카드

탁자 위에 파란 카드와 빨간 카드가 여러 장 놓여 있다. 각 카드에는 $1$보다 큰 정수가 하나씩 적혀 있으며, 같은 수가 여러 카드에 적혀 있을 수도 있다.

파란 카드와 빨간 카드에 적힌 두 수가 $1$보다 큰 공약수를 가질 때, 두 카드를 짝지을 수 있다. 하나의 파란 카드와 짝지을 수 있는 빨간 카드가 여러 장일 수 있고, 그 반대도 마찬가지다. 파란 카드와 빨간 카드를 한 장씩 골라 짝지으면 두 카드는 탁자에서 제거된다.

예를 들어 파란 카드 네 장에 각각 $2$, $6$, $6$, $15$가, 빨간 카드 세 장에 각각 $2$, $3$, $35$가 적혀 있다고 하자. 이때 다음과 같이 짝지을 수 있다. 먼저 $2$가 적힌 파란 카드와 $2$가 적힌 빨간 카드를 짝지어 제거한다. 다음으로 $6$이 적힌 두 파란 카드 중 하나와 $3$이 적힌 빨간 카드를 짝지어 제거한다. 마지막으로 $15$가 적힌 파란 카드와 $35$가 적힌 빨간 카드를 짝지어 제거한다. 이렇게 하면 제거한 짝은 세 쌍이다.

짝짓는 순서에 따라 만들 수 있는 짝의 총 수가 달라짐에 유의하라. 만약 처음에 $15$가 적힌 파란 카드와 $3$이 적힌 빨간 카드를 짝지어 제거하면, 그 뒤로는 한 쌍만 더 제거할 수 있어 총 두 쌍이 된다.

주어진 카드들에서 제거할 수 있는 짝의 최대 개수를 구하여라.

입력은 여러 개의 데이터셋으로 이루어진다. 데이터셋의 개수는 $100$개 이하이다. 각 데이터셋의 형식은 다음과 같다.

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

정수 $m$과 $n$은 각각 파란 카드와 빨간 카드의 개수이며, $1 \le m \le 500$, $1 \le n \le 500$이다. $b_k$ ($1 \le k \le m$)와 $r_k$ ($1 \le k \le n$)는 각각 파란 카드와 빨간 카드에 적힌 수로, $2$ 이상 $10^7$ ($=10000000$) 미만의 정수이다. 입력의 정수들은 공백 또는 줄바꿈으로 구분된다. $b_m$과 $r_n$ 뒤에는 각각 줄바꿈이 온다. 데이터셋에는 그 외의 문자가 없다.

입력의 끝은 공백으로 구분된 두 개의 $0$으로 이루어진 줄로 표시된다.

각 데이터셋에 대해, 만들 수 있는 짝의 최대 개수를 나타내는 정수를 한 줄에 출력한다.