P2065 [TJOI2011] Cards

There are $m$ blue cards and $n$ red cards on the table, each with an integer greater than $1$ on it. You will remove some cards from the table in several steps. Each time, you may remove exactly one pair of cards: the two cards have different colors, and the greatest common divisor of the two numbers on them is greater than $1$. Question: what is the maximum number of pairs you can remove from the table?

The first line contains an integer $T$, the number of test cases. The format of each test case is as follows: > $m\ n$ > $b_1\ b_2\ \ldots\ b_m$ > $r_1\ r_2\ \ldots\ r_n$ The second line gives the numbers on the blue cards, and the third line gives the numbers on the red cards.

For each test case, output the maximum number of pairs of cards that can be removed.

For $100 \%$ of the testdata: $1 \le T \le 100$, $1 \le m, n \le 500$, and each card’s number is greater than $1$ and less than ${10}^7$. Translated by ChatGPT 5