All You Need Is Love

“All you need is love. All you need is love.
All you need is love, love... love is all you need.”
The Beatles

There was invented a new powerful gadget by the International Beautiful Machines corporation called the love machine! Given a string made of binary digits, the love machine answers if it's made only of love, that is, if all you need is love to build that string. The definition of love for the love machine is another string of binary digits, given by a human operator. Let's say we have a string L which represents “love” and we give a string S for the love machine. We say that all you need is love to build S, if we can repeatedly subtract L from S until we reach L. The subtraction defined here is the same arithmetic subtraction in base 2. By this definition, it's easy to see that if L > S (in binary), then S is not made of love. If S = L then S is obviously made of love.

Let's see an example. Suppose S = 11011 and L = 11. If we repeatedly subtract L from S, we get: 11011, 11000, 10101, 10010, 1111, 1100, 1001, 110, 11. So, given this L, all you need is love to build S. Because of some limitations of the love machine, there can be no string with leading zeroes. That is, 0010101, 01110101, 011111, etc. are invalid strings. Strings which have only one digit are also invalid (it's another limitation).

Your task in this problem is: given two valid binary strings, S₁ and S₂, find if it's possible to have a valid string L such that both S₁ and S₂ can be made only of L (i.e. given two valid strings S₁ and S₂, find if there exists at least one valid string L such that both S₁ and S₂ are made only of L). For instance, for S₁ = 11011 and S₂ = 11000, we can have L = 11 such that S₁ and S₂ are both made only of L (as we can see in the example above).

Input Specification

The first line of the input is a positive integer N < 10000 which stands for the number of test cases. Then 2N lines will follow. Each test case consists of a pair of lines. The two lines of the pair stand for the strings (S₁ and S₂) to be entered as input for the love machine. No strings will have more than 30 characters. You can assume that all strings in the input will be valid according to the rules above.

Output Specification

For each string pair, you must print one of the following messages:

Pair #p: All you need is love!
Pair #p: Love is not all you need!

where p stands for the pair number (starting from 1). You should print the first message if there exists at least one valid string L such that both S₁ and S₂ can be made only of L. Otherwise, print the second line.

Sample Input

1. 5
2. 11011
3. 11000
4. 11011
5. 11001
6. 111111
7. 100
8. 1000000000
9. 110
10. 1010
11. 100

download as text file

Output for Sample Input

1. Pair #1: All you need is love!
2. Pair #2: Love is not all you need!
3. Pair #3: Love is not all you need!
4. Pair #4: All you need is love!
5. Pair #5: All you need is love!

download as text file