Same or not

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 2228
64-bit integer IO format: %I64d      Java class name: Main

Description

Everyone konws how to traveling a tree using the DFS strategy. But we also know that there are many ways to do so. For example, giving a tree as the following picture, we may get three ways: 010011, 001101, 01010011. 0 stands for the down operation while 1 means the up operation.
Now we make a constraint: if one node has k direct childs, you can visit a node at most 2*k times, if k == 0, you can visit it only once, in the example, the root has two direct child. Like the example, you can only get two ways: 010011, 001101. Because the way 01010011 will visit the node in yellow four times.
Here is the problem: ACboy drawed a tree, but is not very nice, so he won't show you the picture. Instread he will give you two strings indicating that the ways to travel the tree. Of cource, the strings will only contain 0 and 1. And your mission is to tell whether ACboy is telling the truth. For example, he drawed a picture as the following, if he give you 010011 and 001101, then he is telling the truth, but if he give you 010011 and 01010011, you konw that he is telling a lie.

Input

On the first line of input is a single positive integer n, telling the number of test scenarios to follow.Each test case consists of two lines, each containing a string of the characters '0' and '1' of length at most 3000, both describing a way to travel the tree.

Output

For each test case output a line containing the word "True" or the word "False", depending on whether ACboy is telling the truth.

Sample Input

2
010011
001101
010011
01010011

Sample Output

True
False
Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .