Migrated from Lutece 1556 Excited Pe0ple

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

There is a red team with $N$ people where $i^{th}$ people has a number $A_i$, and a blue team with $M$ people where $j^{th}$ people has a number $B_j$.

If there is a red team member with $A_i$ and a blue team member with $B_j$ that $A_i$ and $B_j$ are not relatively prime, they will be unexcited.

In order to make everyone excited, they remove some people from two teams.

But the removed people are also unexcited, so they want to remove minimum numbers of people.

What is the minimum numbers of people must to be removed so that the remained people are all excited.

Input

The first line contains two numbers $N$ and $M$, indicating the number of red team members and blue team members.

The second line contains $N$ numbers $A_i$.

The third line contains $M$ numbers $B_j$.

$1\leq N, M\leq 10^5, 1\leq A_i, B_j\leq 20000$

Output

The minimum numbers of people must to be removed so that the remained people are all excited.

Samples

1 2
6
2 3

1

Resources

The 15th UESTC Programming Contest Preliminary