Description

Maybe you have known this game.There are n stones on the table. lily and JJ take stones in turn.But they can only take 1,2 or 9 stones at a time.The one get the last stones wins and lily always takes first.The question is weather lily can win.Both lily and JJ are good player of this game.

Input

The first line is a integer t (the number of test cases). Each of the following t lines contains one integer n.(0<n<2^31).

Output

Yes if lily can win,No otherwise.

Sample

Input

5
1
2
3
6
9

Output

Yes
Yes
No
No
Yes

Source: lily