题目描述

在一张无穷大的桌面上，从左往右摆放着无穷张卡片，卡片的编号是 0 至无穷，第 K 张卡片的价值是 3 的 K 次方（即 $3^k$ ）。

对于一个正整数 n 来说，如果可以从桌面上选出若干张不同的卡片，选出来的卡片价值总和等于 n ，那么 n 就称为“好数”。

例如： 3 是“好数”，因为 3=$3^1$ ;

1 是“好数”，因为 1=$3^0$ ;

12 是“好数”，因为 12=$3^2$+$3^1$ ;

但 2 不是“好数”，虽然 2=$3^0$+$3^0$ ，但是 $3^0$ 和 $3^0$ 是相同的卡片，不符合要求。同理， 19 和 20 都不是“好数”。

给出一个 n 个整数，如果是“好数”，输出 YES ，如果不是，输出 NO 。

输入格式

第一行，一个整数 n ( 1 <= n <= 1000 )。

接下来 n 行，每行一个整数 x ( 1 <= x <= 1000000000000000000 )。

输出格式

n 行，每行 YES 或者 NO 。

样例

3
12
13
15

YES
YES
NO