Двоично-троичные числа

Алексей на уроке информатики изучал двоичную и троичную системы счисления. Числа называются интересными, если их запись в троичной системе счисления входит как подстрока в их запись в двоичной. Например, число 9₁₀ = 100₃ = 1001₂.

Алексей, рассматривая множество чисел, для каждого из которых решил определить, является ли число представимым в виде суммы различных интересных чисел. Если да, то необходимо вывести «1», иначе - «0».

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

Входной файл INPUT.TXT содержит в первой строке натуральное число N – количество рассматриваемых чисел (1 ≤ N ≤ 1000).

Во второй строке вводятся N натуральных чисел a_i (1 ≤ a_i ≤ 10⁹), для каждого из которых нужно сказать, является ли число a_i представимым в виде суммы различных интересных чисел.

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

В выходной файл OUTPUT.TXT выведите ответ на задачу в виде строки из нулей и единиц.

Пример

Автор задачи

Владимир Игоревич Лукьянчиков

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]