ADAPLNTS - Ada and Plants 2

no tags 

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 ≤ Ai ≤ 106, the kinds of plants in first furrow.

The next will contain M integers 1 ≤ Bi ≤ 106, 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

hide comments
morass: 2017-10-16 12:59:45

[Rampage] Blue.Mary: Oh, thank you, gotta change it then :P

[Rampage] Blue.Mary: 2017-10-16 05:01:27

The name of this problem coincident with a previous problem.


Added by:Morass
Date:2017-10-08
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Tunisian Collegiate Training Contest - Round #01