Рабочее место участника

Джон заинтересовался разновидностью последовательности Фибоначчи, в которой каждый элемент является является суммой предыдущих, но если сумма является составным числом, то она делится на её наименьший простой делитель.

Для построения такой последовательности задаются два начальных числа `a_0` и `a_1`. Например, `a_0=1` и `a_1=1` получается следующая последовательность:

1, 1, 2, 3, 5, 4, 3, 7, 5, 6, 11, 17, 14, 31, 15, 23, 19, 21, 20, 41, 61, 51, 56, 107, 163, 135, 149, 142, 97, 239, 168, 37, 41, 39, 40, 79, 17, 48, 13, 61, 37, 49, 43, 46, 89, 45, 67, 56, 41, 97, 69, 83, 76, 53, 43, 48, 13, 61, 37, …

При сложении чисел 3 и 5 на 4-м шаге получается число 8, которое имеет делитель 2, поэтому `a_5`=4. При сложении чисел 5 и 4 на 5-м шаге получается число 9, которое имеет делитель 3, поэтому `a_6`=3.

В отличие от обычной последовательности Фибоначчи, в которой числа возрастают бесконечно, в простой последовательности Фибоначчи вскоре появляется цикл.

Напишите программу, которая поможет Джону найти циклы в простой последовательности Фибоначчи, которая начинается с заданных начальных чисел.

Первая строка ввода содержит целое число `N` (`1\ ≤\ N\ ≤\ 1000`). Каждая из `N` последующих строк содержит два целых числа `a_0` и `a_1` (`1\ ≤\ a_0,\ a_1\ ≤\ 1000`) – начальные числа последовательности.

Для каждой пары начальных чисел последовательности вывести на отдельной строке два числа `i` и `j` – индексы начала и конца цикла, т.е. наименьшие номера элементов последовательности, для которых `i<j` и `a_{i-1}=a_{j-1}` и `a_i=a_j`.

3
1 1
2 2
15 17

38 56
1 2
1 137