You are given a string S with only 0 and 1. You can delete the string 100 from any position of S an infinite number of times and obtain a new S after concatenation. Is it possible to make the string empty?

As for example, if S=101000 then 101000->100->empty

If S=1010001 then 1010001->1001->1->not empty

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case contains a string S. The size of string is at most 120000.

Output

For each test case, print the case number and “yes” if it is possible to make the string S empty, print “no” otherwise.

Problem Setter: Md Abdul Alim, Dept. of Computer Science, Bangladesh University of Business & Technology