URI Online Judge | 2730

Paired Pairs

By Marianne Linhares, UFCG BR Brazil

Timelimit: 2

Maria Luisa loves math, she just won two sets of integers: set and set B, both sets have the same number of elements. She's playing a game where she creates pairs using elements from these sets.

But this game was not so fun as she thought, to make this interesting Maria Luisa defined a concept of a paired pair. A pair is paired if the greatest common divisor of the integers from the pair is 1. For instance: (2, 4) is not a paired pair, but (3, 5) is a paired pair.

Maria Luisa wants your help to know how many paired pairs there are such that one pair is composed of an element of and an element of B. Two pairs (p1, p2) and (p3, p4) are equal if p1 = p3 and p2 = p4.

Here's a complete example:

A = {3, 2}
B = {2, 5}

The answer is: 6 and all the possible paired pairs are: (3, 2) (2, 3) (3, 5) (5, 3) (2, 5) (5, 2).


The input consists of several lines. The first line contains an integer N (1 ≤ N ≤ 200) representing the number of elements in the sets. The second line contains positive integers that belong to A and the third line contains positive integers that belong to B.

N=0 ends the input. All numbers are 32 bits integers.


The number of different paired pairs that can be obtained using a number from and a number from B.

Input Sample Output Sample


1 2 3 4 5

2 4 6 8 10


3 2

2 5