Vasya often visits Petya. In order to get to Petya's yard, you need to enter the code,
consisting of four digits. Usually friends went together, but this time Vasya came alone, and
Petya is waiting for him at home.
Vasya does not remember the code, but he has several options. In addition, for some reason, Vasya remembered
the fact that the square of the number composed of the first two digits of the code, in the sum of the square of the number,
consisting of the last two digits of the code, when divided by seven, the remainder is one. That is, if the code
represents "ABCD" where "A", "B", "C", "D" — some digits, then AB2+CD2 has
remainder 1 when divided by 7. For example, code 2843 is one of the possible codes because
282 + 432 = 2633 = 376 · 7 + 1, and 8243 — no, because 822 + 432 = 8573 = 1224 · 7 + 5.
Vasya has several options for what the code could be. Help him identify which
one of the options may be the code from the entrance to Petin Dvor.
Input data format
The first line of contains the number t (1 ≤ t ≤ 10 000) — number of code options,
that Vasya remembers. The next t lines contain four digits — code options.
Output Format
Print t lines in your answer. On the i-th line print "YES" if the i-th code can be a code
to enter Petin Dvor, otherwise print "NO",
Examples
Input:
3
2843
8243
0100
Output:
YES
NO
YES