Charlie wants to order chocolates from Mr. Willy Wonka's Chocolate Factory but he's facing a dilemma here. One of the Oompa Loompas has informed Charlie that chocolates are shipped only in specific numbers that satisfy a certain special sequence.

This special sequence has the first n terms as digits of the number, and the next terms are calculated as the sum of the previous n terms.

Help Charlie find out whether he can order x number of chocolates.

INPUT

The first line of input contains an integer t, the number of test cases. Then t test cases follow with each line having an integer x.

OUTPUT

For each test case in a new line, print 1 if the number satisfies the sequence, else print 0

CONSTRAINTS

1 <= t <= 5000
1 <= x <= 10000

SAMPLE INPUT

3
197
10
14

SAMPLE OUTPUT

1
0
1

EXPLANATION

(i) 197 -> (1, 9, 7, 17, 33, 57, 107, 197) -> Yes (1)

(ii) 10 -> (1, 0, 1, 1, 2, 3, 5, 8, 13, ....) -> No (0)

(iii) 14 -> (1, 4, 5, 9, 14) -> Yes (1)