J. Spilt the String
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a string s consisting of lowercase English letters and spaces, find a way to split the string s into multiple lines of the same length. Leading and trailing spaces are ignored while computing the length of the new lines.

Note that you cannot split words, for example if s contains the word "amman", the whole word must be on the same line.

If there is a way to split s into multiple lines print "YES" (without the quotes), otherwise print "NO" (without the quotes).

Input

The first line of the input contains an integer T (1  ≤  T  ≤  250), where T is the number of the test cases.

Each case has one line that contains a string s. All strings are non-empty and the length of each of these strings does not exceed 105 characters.

It is guaranteed that there is only one space between any two words, and there are no leading or trailing spaces in s.

Output

Print T lines, on each line print "YES" (without the quotes) if you can split the given string s into multiple lines of the same length. Otherwise, print "NO" (without the quotes).

Example
Input
2
acm arab collegiate programming contest
acm amman collegiate programming contest
Output
YES
NO
Note

In first test case, "acm arab collegiate programming contest", the only possible solution is:

acm arab collegiate

programming contest

In second test case, "acm amman collegiate programming contest", there is no solution.