Задача C. Салаты

Автор:Тимофей Бажеко   Ограничение времени:0.1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

"Не трогать! Это на Новый Год!" - грозно сказала мама Свете, убирая n крабовых палочек в холодильник. Света очень любит крабовые палочки, но еще больше она любит их в салатах. Она с нетерпением ждала, когда мама закончит их готовить. В этом году мама готовит салаты по определенной схеме. Кладет крабовые палочки в каждый последующий салат так, что в нем оказывается сумма палочек из двух предыдущих салатов. Она назвала это Салаты Фибоначчи. Вот бы Свете выяснить, какая это по счету партия крабовых палочек лежит в холодильнике.

Числа Фибоначчи — это последовательность чисел, которые задаются по определённому правилу. Оно звучит так: каждое следующее число равно сумме двух предыдущих. Первые два числа заданы сразу и равны 0 и 1. Последовательность Фибоначчи выглядит следующим образом 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, ... , ∞

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

Первая строка входного файла содержит натуральное число q - количество чисел Фибоначчи. Во второй и последующих строках указаны числа из последовательности Фибоначчи (одна строка - одно число) .

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

Выведите порядковый номер, начинающийся с 0, для каждый строки (одна строка - один порядковый номер, соотвествующего числа Фибоначчи). PS: В случае числа 1, когда невозможно точно определить место в последовательности, необходимо вывести текст unknown.

Ограничения

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.

По запросу сообщается результат окончательной проверки на каждом тесте.

Подзадача Баллы Дополнительные ограничения
nq
1100 ≤ n ≤ 1091 ≤ q ≤ 80
2350 ≤ n ≤ 101261 ≤ q ≤ 160
3550 ≤ n ≤ 1012541 ≤ q ≤ 200

Пояснение к примерам

Для первого примера: 0 является начальным числом Для второго примера: для 1 невозможно определить место, поэтому unknown Для третьего примера: число 13 является 7-ым числом, а 233 13-ым числом (считая с нуля) в последовательности Фибоначчи 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

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

Стандартный вход Стандартный выход
1
1
0
0
2
1
1
unknown
3
2
13
233
7
13

0.090s 0.009s 13