Recently, Kostya learned that there are numbers whose representation in the ternary numeral system appears as a substring in their representation in the binary system. He called such numbers beautiful. For example, the number 12₁₀ = 110₃ = 1100₂ is beautiful because the string “110” is a substring of “1100”.

Now Kostya decided to come up with an interesting definition related to beautiful numbers, after which he would create a problem in computer science based on it. He called a number X wonderful if it can be expressed as a sum of distinct beautiful numbers. According to this definition, the number 22 = 10 + 12 is wonderful, while the number 3 is not. It is also worth noting that by definition, all beautiful numbers are also wonderful.

Your task is to determine for several natural numbers whether they are wonderful or not.

The first line contains a single integer N — the number of numbers being considered (1 ≤ N ≤ 1000).

The second line contains N integers x_i, for each of which you need to determine whether it is wonderful (1 ≤ x_i ≤ 10⁹).

In the i-th line, you need to output one string “YES” if the number x_i is wonderful, or the string “NO” otherwise.