Ada the Ladybug is a farmer. She has two furrows with plants. Each plant has some kind (denoted by number). Problem is, that as soon as there is a pair of plants with gcd greater than 1 in distinct furrows none of them will grow. Ada has decided to throw away minimal number of plants so that every remaining plant will grow up.

She has asked you to count the maximal number of plants which could grow up.

Input

The first line of each test-case will contain two integers 1 ≤ N M ≤ 800, the number of plants and first and in second furrow.

The next will contain N integers 1 ≤ A_i ≤ 10⁶, the kinds of plants in first furrow.

The next will contain M integers 1 ≤ B_i ≤ 10⁶, the kinds of plants in second furrow.

Output

For each test-case, print the maximum number of plants which could grow up.

Example Input

3 4
3 4 5
6 30 1 7

Example Output

5

Example Input

4 3
2 2 10 32
4 16 28

Example Output

4

Example Input

5 5
2 6 12 15 18
33 8 2 3 5

Example Output

5

Example Input

3 3
2 27 9
3 4 8

Example Output

4