We define a repeated number as a positive integer consisting of two or more instances of the same digit concatenated together. For example, 11 and 4444 are repeated numbers, while 5 and 11222 are not.

Given a positive integer n, your task is to find all repeated numbers that have fewer digits than n has.

Input

First an integer t (1 ≤ t ≤ 100), then on each of the next t lines an integer n (1 ≤ n < 10¹⁸).

Output

For each test case, print all repeated numbers that have fewer digits than n has, in ascending order.

Score

Your score is your source length.

Example

Input:

2
100
1234

Output:

11
22
33
44
55
66
77
88
99
11
22
33
44
55
66
77
88
99
111
222
333
444
555
666
777
888
999