АВТ ВоГУ - Задача 1606. Палиндромы Фибоначчи

Рассмотрим следующие строки, состоящие из цифр 0 и 1:

S₀ = "0"
S₁ = "01"
S₂ = S_1S₀ = "010"
S₃ = S_2S₁ = "01001"
S₄ = S_3S₂ = "01001010"
S₅ = S_4S₃ = "0100101001001"
...
S_n = S_{n - 1}S_{n - 2}
...

Как видно из определения, строка S_{n - 1} является префиксом строки S_n для любого n > 0. Значит, существует бесконечная строка S_∞, являющаяся пределом строк S_n, то есть такая, что для любого n ≥ 0 строка S_n является префиксом S_∞.

(Если предыдущее определение не удалось понять, то можете считать, что S_∞ — это просто S_n для достаточно большого n, скажем, n = 10¹⁰⁰)

Строка S_∞ называется строкой Фибоначчи.

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

Входные данные

В первой строке находится натуральное число n — количество подстрок (1 ≤ n ≤ 10⁴). Далее заданы сами строки. Каждая из них задана двумя числами start и len и соответствует подстроке строки S_∞, начинающейся с позиции start (позиции нумеруются с единицы) и состоящей из len символов (1 ≤ start, len ≤ 10⁹).

Выходные данные

Выведите n строк, по одной для каждой входной подстроки. Для очередной подстроки выведите "TAK", если она является палиндромом, и "NIE" в противном случае.

Пример

Входные данные

Выходные данные

TAK
NIE
TAK
TAK

Дистанционный практикум по программированию

1606. Палиндромы Фибоначчи