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.

Example

Input:
2
101000
1010001
Output:
Case 1: yes
Case 2: no

Problem Setter: Md Abdul Alim, Dept. of Computer Science & Engineering, BUBT