Cards

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.

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.

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