Cards

Interview

Time limit5sMemory limit128 MB

Summary

Given blue and red cards with numbers, find the maximum number of blue-red pairs whose two numbers share a common divisor greater than 1.

Level: Medium7 of 10
Topics: Graph, Number theory, Dynamic programming, BFS
Solved: No attempts yet

Problem

There are many blue cards and red cards on the table. On each card an integer greater than $1$ is printed, and the same number may appear on several cards.

A blue card and a red card can be paired when the two numbers printed on them have a common divisor greater than $1$ . One blue card may be pairable with several red cards, and one red card may be pairable with several blue cards. When a blue card and a red card are chosen and paired, both cards are removed from the table.

For example, suppose four blue cards show $2$ , $6$ , $6$ , and $15$ , and three red cards show $2$ , $3$ , and $35$ . Then the cards can be paired as follows. First, pair the blue card showing $2$ with the red card showing $2$ and remove them. Next, pair one of the two blue cards showing $6$ with the red card showing $3$ and remove them. Finally, pair the blue card showing $15$ with the red card showing $35$ and remove them. In this way three pairs are removed.

Note that the total number of pairs depends on the order in which cards are paired. If the blue card showing $15$ and the red card showing $3$ are paired and removed first, then only one more pair can be removed afterwards, for a total of two pairs.

Your task is to find the largest number of pairs that can be removed from the given set of cards.

Input

The input is a sequence of datasets. The number of datasets is at most $100$ . Each dataset has the following format.

m n
b1 ... bk ... bm
r1 ... rk ... rn

The integers $m$ and $n$ are the numbers of blue cards and red cards, respectively, with $1 \le m \le 500$ and $1 \le n \le 500$ . Each $b_k$ ( $1 \le k \le m$ ) and $r_k$ ( $1 \le k \le n$ ) is the number printed on a blue card or a red card, an integer at least $2$ and less than $10^7$ ( $=10000000$ ). The integers in the input are separated by a space or a newline. Each of $b_m$ and $r_n$ is followed by a newline, and the dataset contains no other characters.

The end of the input is indicated by a line containing two zeros separated by a space.

Output

For each dataset, output on a single line an integer that is the maximum number of pairs.

Examples3

Example 1

Input

4 3
2 6 6 15
2 3 5
2 3
4 9
8 16 32
4 2
4 9 11 13
5 7
5 5
2 3 5 1001 1001
7 11 13 30 30
10 10
2 3 5 7 9 11 13 15 17 29
4 6 10 14 18 22 26 30 34 38
20 20
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
100 100
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
117 755 835 683 52 369 302 424 513 870
75 874 299 228 140 361 30 342 750 819
761 123 804 325 952 405 578 517 49 457
932 941 988 767 624 41 912 702 241 426
351 92 300 648 318 216 785 347 556 535
166 318 434 746 419 386 928 996 680 975
231 390 916 220 933 319 37 846 797 54
272 924 145 348 350 239 563 135 362 119
446 305 213 879 51 631 43 755 405 499
509 412 887 203 408 821 298 443 445 96
274 715 796 417 839 147 654 402 280 17
298 725 98 287 382 923 694 201 679 99
699 188 288 364 389 694 185 464 138 406
558 188 897 354 603 737 277 35 139 556
826 213 59 922 499 217 846 193 416 525
69 115 489 355 256 654 49 439 118 961
0 0

Expected output

Example 2
Input
```
1 1
6
3
0 0
```
Expected output
```
1
```
Example 3
Input
```
1 1
2
3
0 0
```
Expected output
```
0
```