| Автор: | Тимофей Бажеко | Ограничение времени: | 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.
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
| Подзадача | Баллы | Дополнительные ограничения | |
|---|---|---|---|
| n | q | ||
| 1 | 10 | 0 ≤ n ≤ 109 | 1 ≤ q ≤ 80 |
| 2 | 35 | 0 ≤ n ≤ 10126 | 1 ≤ q ≤ 160 |
| 3 | 55 | 0 ≤ n ≤ 101254 | 1 ≤ q ≤ 200 |
Для первого примера: 0 является начальным числом Для второго примера: для 1 невозможно определить место, поэтому unknown Для третьего примера: число 13 является 7-ым числом, а 233 13-ым числом (считая с нуля) в последовательности Фибоначчи 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|
| 2 | |
|
| 3 | |
|