Vace has recorded a lot of phone numbers. On her notebook, the numbers are divided by hyphens. Then, she began to doubt whether her records are correct. After all, there are different numbers which are pronounced in the same way. For example, 3000-100-1, 3000-101, 3100-1, 3101 are all read as "three thousands, one hundred, one." Now she wants to find out what numbers are pronounced the same as the recorded number.
Vace believes that there would be no number consisting of more than nine digits in the pronunciation of a phone number. And here is how Vace pronounces numbers 1 through 999999999.
If the number is greater than or equal to 1 million, the first part is to pronounce the number of millions, then the word "million" according to the following rules. If the number of millions, taken modulo 10, is 1, then pronounce the word "million." If the number of millions, taken modulo 10, is 2, 3 or 4, then pronounce the word "millioni." Otherwise pronounce the word "milliono."
If the number, taken modulo 1 million, is greater than or equal to 1000, then pronounce the number of thousands and the word "thousand" according to the following rules. If the number of thousands, taken modulo 10, is 1, then pronounce the word "thousand." If the number of thousands, taken modulo 10, is 2, 3 or 4, then pronounce the word "thousandi." Otherwise pronounce the word "thousando."
Finally, if the number, taken modulo 1000, is different from zero, then pronounce the number. Note that the numbers from 11 to 19 is spoken as a word, also do the numbers 20, 30, ..., 90. For example, the number 978121014 pronounced "nine hundred seventy eight milliono one hundred twenty one thousand fourteen," and the number 1000142 pronounced "one million one hundred forty two."
Help Vace to find all the phone numbers, which are pronounced the same as the one in her records.
The first line of the input file contains an integer T, which is the number of test cases.
Each test case takes one line, containing several numbers separated by hyphens `-'. Each number in the record contains no more than nine digits, and does not have leading zeros. It is guaranteed that the numbers in Vace's record have at most 50 digits.
For each test case the first line of the output should contain a number N,
which is the number of phone numbers pronounced the same as the recorded one.
Each of the following N lines should contain a phone number.
Each phone number should consists of the numbers from 1 to 999999999, separated by hyphens.
The phone numbers should be listed in lexical order.
It is guaranteed that the number of solutions of each test case does not exceed 100000.
Note that the solutions may consist of more than 50 digits.
1 3000-101
4 3000-100-1 3000-101 3100-1 3101
Migrated from old NTUJ.
All-Russian Olympiad team programming 2011
| No. | Testdata Range | Score |
|---|