Задача G5. Fractional multiplication ≡

Условие

Имеется набор из N рациональных дробей, каждая из которых задается своим числителем A_i и знаменателем B_i.

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

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

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

Входные данные содержит целое число N, за которым следует набор из N пар целых чисел (A_i, B_i).

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

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

Ограничения

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

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

1
35880 17940

0

1
76824 12804

1

1
94803 11573

2