Anna University Local Contest #10

Given a number, find if it is possible to convert it into a mono-number. If all the digits of a number are same, it is a mono-number.

Examples: 666, 7, 11, 55555555555555555555.

Only one operation is allowed: You can replace two adjacent digits of the number by their sum. Digit(s) that are a result of sum of two digits cannot be involed in any further operations. There is no limit on the number of operations.

Example:

123 => (1+2)3 => 33

675 => 6(7+5) => 613 

(Though this is a valid operation, it is useless as we can never get a mono-number this way as the resultant itself has two different digits)

Input

First line contains T, the number of test cases.

Next T lines contain N, the number that should be converted to a mono-number.

Output

For each test case a line:

If it is possible, output "YES", else output "NO".

Constraints

T can be as high as 1000.

N can have upto 20 digits.

Example

Input:
4
123
23232323232323
7734716752
12345678

Output:
YES
YES
YES
NO

Explanation

First test case is explained in the problem statement.

In second, all the digits can be made 5, by adding adjacent 2 and 3s.

In third, all digits can be converted to 7.