Common scores P95498

Statement

thehtml

Two friends, Arthur and Bob, are playing computer games, and they have decided to store their scores. When they stop playing, Arthur and Bob want to determine the length of the maximum subsequence of scores that they have in common.

For instance, if the scores of Arthur are [8, 12, 6, 9, 2], and those of Bob are [12, 6, 8, 2], then the maximum subsequence that they have in common is [12, 6, 2], which has length 3. Note that a subsequence does not have to be made up of consecutive elements, but we must preserve the order of the scores.

Input

Input consists of several cases. Each case begins with two numbers 0≤ M≤ 1000 and 0≤ N≤ 1000, representing the length of the subsequences of Arthur and Bob, respectively. Follow the M numbers of Arthur, and the N numbers of Bob. All the numbers are natural.

Output

For every case, print the length of the longest common subsequence.

Public test cases

Input

5 4
8 12 6 9 2
12 6 8 2
7 7
8 13 16 7 12 9 5
16 7 9 5 8 13 16
15 12
11 9 12 6 2 6 12 19 2 7 1 16 12 15 2
9 6 18 6 12 17 19 8 7 12 3 15

Output

3
4
8

Information

Author: Anders Jonsson
Language: English
Translator: Carlos Molina
Original language: Spanish
Other languages: Spanish
Official solutions: C++ Python Python
User solutions: C++ Python