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, Dept. of Computer Science, Bangladesh University of Business & Technology


hide comments
---@@@----: 2015-05-30 14:16:47

getting tle...
how to optimize??

Lehar: 2015-03-01 21:50:23

AC in one go! :D
Nice ques!

:.Mohib.:: 2015-02-18 16:48:46

Nice question...enjoyed... :)

Gaurav sharma: 2015-02-07 20:03:52

easy one....green light in 1 go :)

darol: 2015-01-22 23:48:23

6,4s for 120000 characters at one pass. meh... need study more.


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