Недавно Костя узнал, что существуют числа, запись которых в троичной системе счисления входит как подстрока в их запись в двоичной. Он назвал такие числа красивыми. Например, красивым является число 12₁₀ = 110₃ = 1100₂, так как строка «110» является подстрокой «1100».

Теперь Костя решил придумать интересное определение, связанное с красивыми числами, после чего составить из этого задачу по информатике. Он назвал число X прекрасным, если оно представимо в виде суммы различных красивых чисел. Согласно такому определению, прекрасным является, например, число 22 = 10 + 12, а число 3  — нет. Также стоит отметить, что по определению все красивые числа также являются прекрасными.

Ваша задача заключается в том, чтобы определить для нескольких натуральных чисел, являются они прекрасными или нет.

В первой строке вводится одно целое число N  — количество рассматриваемых чисел (1 ≤ N ≤ 1000).

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

В i-й строке нужно вывести одну строку «YES», если число x_i является прекрасным, или строку «NO» в противном случае.