BINA - Binary Again

One day I was playing card game on the computer of ACM ICPC Training Lab and my friend Istiyak was thinking something. Suddenly he said, “Munna, can you tell me whether A is divisible B or not?”.

Then I said to him, “That’s very simple! tell me A and B”. Then he said, “That’s not simple as you are thinking. I will tell you the binary of A and B”. Then he asked me that can I do it now?

I am not the man who can be defeated easily. But I also don’t know how to do it. As you are a good friend of mine. You are going to complete this task in my favor.

Input

On the first line you will be given the test case number T (T < 255).

Then for each test case you will be given two set of binary number, one on each line. Each set of binary will fit in 64 bit integers.

Output

For each test case print the test case number and print “YES” if A is divisible by B, otherwise print “NO” without quotes.

Example

Input:
3
11010
10
1111
11
111
11

Output:
Case 1: YES
Case 2: YES
Case 3: NO

Problem Setter: Monjurul Huda Munna

Special thanks: MD Istiyak Ahmed, Shuvo Karmakar. Daffodil International University, Dhaka


Added by:shuvo karmakar
Date:2015-06-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY

hide comments
2015-11-15 23:01:27 shuvo karmakar
In C/C++ long long is enough for solve this problem :)
2015-10-25 16:48:14
solved in python but in c++ number cross 64 bit number
2015-07-23 19:30:47
using long in java as 64 bit should solve the problem...but it is continuously giving a wrong answer . A solution to this problem should be provided in every language.
2015-06-20 19:38:49 Sandip Jana
THANKU FOR UPDATING DATA SET. GOT USELESS NZECS IN JAVA :(
2015-06-20 17:51:33 shuvo karmakar
Thanks @Vipul Srivastava and sorry for inconvenience. I just update the data set. Now its ok.
2015-06-20 16:10:50 rk
sry i forgot plz put this to tutorial also
2015-06-20 16:10:04 rk
assume if b is all zero answer is "NO assuming yes costed costed me 4 wa

Last edit: 2015-06-20 17:58:15
2015-06-20 13:00:59 Vipul Srivastava
@ Sidhanta Chaudhary. Yes it can
2015-06-20 12:55:08 Sidhanta Choudhury
B contains all zero? then how can divide A by zero

Last edit: 2015-06-20 13:16:25
2015-06-20 10:42:54 Vipul Srivastava
Ya python is giving nzec please setter look for empty lines in the test cases
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.