EMTY - Can You Make It Empty 1

no tags 

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 100.

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


hide comments
PKJ: 2016-06-13 03:47:59

it is being accepted for 01 --> yes. pls correct it

Md Abdul Alim: 2014-10-08 11:30:04

After solve this, you can try
http://www.spoj.com/problems/EMTY2/


Added by:Alim
Date:2014-03-03
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C C++ 4.3.2 CPP JAVA
Resource:Own Problem