Задача G5. Fractional multiplication ≡

Условие

Имеется набор из $N$ рациональных дробей, каждая из которых задается своим числителем $A_{i}$ и знаменателем $B_{i}$.

Требуется написать программу, которая выводит:

• 0 — если произведение всех этих дробей дает единицу либо простое число;
• 1 — если это составное целое число;
• 2 — если это дробное число.

Формат входных данных

Входные данные содержит целое число $N$, за которым следует набор из $N$ пар целых чисел $(A_{i},\,B_{i})$.

Формат выходных данных

Выходные данные должны содержать единственное число — ответ задачи.

Ограничения

$1 \le N \le 200$, $1 \le (A_{i},\,B_{i}) \lt 2^{32}$

Примеры тестов

1
35880 17940

0

1
76824 12804

1

1
94803 11573

2