The cats really love to play with numbers. Recently they are practicing high-speed addition and the cats discovered some amazing results. They are trying to add continuous integral numbers from A to B. For example, letting A=1 and B=5 the result is 15; letting A=2 and B=7 the result is 27. It seems that some of the (A, B) pair that the summation from A to B inclusively results in the concatination of A and B when write them down in decimal numbers. The cats are so happy that they call the (A, B) pair a cat number pair!
Given the digits of A and B written in decimal, can you figure out all the cat number pairs?
The first line contain an integer T<=100, the each of next line contains two integers X and Y indicating the number of digits of A and B respectively. (1<=X<=Y<=16).
For each test case, please output all possible solution (A, B) satisfies the input condition. If there is no answer, please output "No cats." in a single line. Please don't outpu t any redundant empty lines. Note that A is always less than B and the output in a test case should be sorted according to the concatinated number AB.
4 1 1 1 3 1 4 2 2
1 5 2 7 7 119 No cats. 13 53 18 63 33 88 35 91
Migrated from old NTUJ.
東大programming contest 2009
| No. | Testdata Range | Score |
|---|