Eureka Theorem

The triangular number $T_n$ ($n \ge 1$) counts dots stacked in the shape of a triangle: 1 dot in the first row, 2 in the second row, and $n$ dots in the $n$th row.

$T_n = 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$

In 1796 Gauss proved that every natural number is the sum of at most three triangular numbers. For example:

• $4 = T_1 + T_2$
• $5 = T_1 + T_1 + T_2$
• $6 = T_2 + T_2$ or $6 = T_3$
• $10 = T_1 + T_2 + T_3$ or $10 = T_4$

Gauss wrote "Eureka! num = $\Delta + \Delta + \Delta$" in his diary to mark the proof, and the result is known as the Eureka theorem because of that line. Kkung wondered which natural numbers are the sum of exactly three triangular numbers. In the examples above, 5 and 10 are such sums, but 4 and 6 are not.

Given a natural number, write a program that decides whether it is the sum of exactly three triangular numbers. The three triangular numbers do not have to be distinct.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains one natural number $K$ ($3 \le K \le 1000$).

Print one line per test case. Print 1 if $K$ is the sum of exactly three triangular numbers, and 0 otherwise.