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.

Sample Input

Output for Sample Input

2
101000
1010001

Case 1: yes
Case 2: no



Problem Setter: Md Abdul Alim, CEO and Founder at CodeMask


hide comments
iamwaste: 2019-02-08 19:53:28

interesting question - think about automata theory while doing - AC on second attempt

payal2621: 2018-01-29 15:41:52

guys getting tle use this "ios_base::sync_with_stdio(false);"

sedulous_001: 2017-09-25 16:21:18

Yes, there is white space between " Case x: " & "yes/no". Got wrong answer twice :(

vinuvarsidh: 2017-09-17 16:49:01

iam getting wrong answer.. though i print it as Case 1: yes can anyone tell me why

mahilewets: 2017-08-30 11:17:03

Sample output looks like there is no whitespace between "Case X:" and "yes/no"

But there is

And if you do not output whitespace after ":" you are WA

nikhil2504: 2017-07-07 02:10:24

Stack kills it!

vengatesh15: 2017-01-21 17:59:10

AC in 1 go:-)

madhavgaba: 2016-12-16 09:11:01

Did without stacks in O(n)........just count number of zeros and ones :D

dwij28: 2016-10-16 22:50:20

Standard Problem on Stacks.

Anushka: 2016-07-03 14:16:09

There is a space after ':'.. Costed me a useless WA


Added by:Md Abdul 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