ADAPLNTS  Ada and Plants 2
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 testcase 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^{6}, the kinds of plants in first furrow.
The next will contain M integers 1 ≤ B_{i} ≤ 10^{6}, the kinds of plants in second furrow.
Output
For each testcase, 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:
20171016 12:59:45
[Rampage] Blue.Mary: Oh, thank you, gotta change it then :P 

[Rampage] Blue.Mary:
20171016 05:01:27
The name of this problem coincident with a previous problem. 
Added by:  Morass 
Date:  20171008 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Tunisian Collegiate Training Contest  Round #01 