Problem G5. Fractional multiplication ≡

Statement

There is a set of N rational fractions, each is represented by corresponding numerator A_i and denominator B_i.

You must write a program that outputs:

• 0 — if the product of all fractions is either 1 or a prime;
• 1 — if it is integer non-prime;
• 2 — if it is a fractional number.

Input format

Input contains integer N, followed by N pairs of integers (A_i, B_i).

Output format

Output must contain a single integer — answer to the problem.

Constraints

1 ≤ N ≤ 200, 1 ≤ (A_i, B_i) < 2³²

Sample tests

1
35880 17940

0

1
76824 12804

1

1
94803 11573

2