Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Джон заинтересовался
разновидностью последовательности Фибоначчи, в которой каждый элемент является
является суммой предыдущих, но если сумма является составным числом, то она делится на её наименьший простой делитель.
Для построения такой последовательности задаются два начальных числа `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