EMTY2 - Can You Make It Empty 2

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


Added by:Alim
Date:2014-03-03
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:Own Problem

hide comments
2016-12-16 09:11:01
Did without stacks in O(n)........just count number of zeros and ones :D
2016-10-16 22:50:20
Standard Problem on Stacks.
2016-07-03 14:16:09 Anushka
There is a space after ':'.. Costed me a useless WA
2016-06-13 23:53:24
For those getting tle using stack, change your stack approach to the vector approach. Although such problems are always solved using stack, but it worked for me. Popping the elements can be replaced by a similar approach in vectors. :-)
2016-05-17 16:10:08
Easy one - O(n) !!
AC in 1st attempt!!!


Last edit: 2016-05-17 16:11:15
2015-12-22 15:53:51
Trying to do it using stack ...can anyone provide me with testcases....can't understand what went wrong
2015-09-25 16:14:41 Aditya Kumar
Its direct!! O(N)
2015-08-11 13:32:27
Finally my 50th...... ;)
2015-06-10 17:17:50 Vipul Srivastava
there is a 'space' after ':' got many WA due to this
2015-06-08 14:58:06 BRAIN
O(n) :"> 0.00s
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.