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


hide comments
orifxon_2007: 2023-07-10 12:49:14

but what about 001100?

sanjeev30798: 2020-01-12 18:42:09

counting zeroes and ones would not help. For numbers like 100001, counting would give yes but the answer is no.

prachij: 2019-12-17 09:27:56

Solved it just by counting :)

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:-)


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