In the world of Hirok Rajar Deshe, there is a king who is a coder. He has decided that he would make a sequence of numbers and test the people of his country, who has to tell the next number of the sequence. If someone fails, he will be given the harshest punishment of Mogoj Dholai.
The test contains a number at any position of the sequence, possibly of an invalid sequence, as well (because the king is very tyrant and wants to confuse normal citizen). The citizens have to say the next number of the sequence.
The rule of the sequence follows like this: Given a number with numerical digits. The digits of the next number will come in pairs. Each of the pair will be, how many continuous digits are there of any digit in the previous number, followed by the digit itself.
Say, a given number is 1113422. The next number will be generated by the following procedure: Three (3) Ones (1), One(1) Three(3), One(1) Four(4), Two(2) Twos(2). So, the next number will be 31131422. A number is invalid if the number of continuous digits of a digit is greater than a single digit number. Now you are the Master Moshai, a hero. Your job is to write a program that will save the citizens from the punishment.
Input
First line contains a number T,number of test cases.
Next T lines contain a positive integer with N digits. No digit of the number contain zero.
Constraints:
1 ≤ T ≤ 500
1<=N<=45000
Output
Print the case number and next number of the sequence.
If invalid print -1.
Sample
| Input | Output |
|---|---|
3 1113422 566666666661 15 | Case 1: 31131422 Case 2: -1 Case 3: 1115 |
For the 2nd case there are 10 continuous 6’s. So the second case is invalid.
