After Maryanna found the treasure buried by 27 pilots in a secret cave, she wanted to leave there immediately. Unfortunately, finding the door closed because of the overweight treasure she carried, she had to find out the password of the lock. She remembered someone had told her the password is an N-digit natural decimal integer (without extra leading zeroes), and the N least significant digits of any positive integral power of that integer is same as itself. She, being a smart girl, came up with all the possible answers within 1 minute. After a few times of tries, she escaped from that cave successfully. To show your intelligence you may solve the same task with your computer within only 10 seconds!

Input

The first line contains T (T <= 1000), the number of test cases. T lines follow, each contains a single positive integer N(N <= 500).

Output

For each test case, output a single line, which should begin with the case number counting from 1, followed by all the possible passwords sorted in increasing order. If no such passwords exist, output Impossible instead. See the sample for more format details.

Example

Input:
2
2
1
Output:
Case #1: 25 76
Case #2: 0 1 5 6