REPNUM - Repeated Numbers

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 < 1018).

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

Added by:avinash
Date:2013-02-20
Time limit:1s
Source limit:140B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:GAWK C C++ 4.3.2 CPP C99

hide comments
2014-11-04 19:07:24 Mitch Schwartz
Problem statement updated. Although easy to solve, it has some interesting features for golf in various languages.
2014-11-04 00:21:30 Francky
@min_25 (about the reply to Mitch) : In that case, IO files could be broken, as with 13, we are waiting for only 11, not 11 22 ... 99.
2014-11-03 23:49:21 Min_25
@Mitch
Yes, I assumed that.
(I didn't use the value of n; I printed all repeated numbers m such that 11 <= m < 10^(len(str(n))-1) in ascending order.)

Edit:
@Francky
Yes, I/O files could be broken if n could be arbitrary integer (<= 10^19).

I assumed that every n has a form of 10^e because the description says that "n will be the lowest number of any digit." (unclear sentence).

However, that seems not to be the case.

Last edit: 2014-11-04 00:48:52
2014-11-03 23:16:18 Mitch Schwartz
Integer t on first line, then t lines each containing some integer n, and we print in ascending order the repeated numbers x such that 11 <= x <= n ?

@Min_25: Thanks! I can update the problem statement when I have time; the description is not clear.

Last edit: 2014-11-04 00:19:06
2014-11-03 21:17:22 Min_25
The I/O files seem to be O.K.

EDIT:
The I/O files seem to be broken with the current description.

Last edit: 2014-11-04 00:52:47
2014-05-23 15:32:40 Sergey Skupoy
Can anybody tell me how program should read input data? For example if I have a solution in AWK, the script needs to read certain lines of input file, which lines (line numbers)?

Last edit: 2014-05-23 15:33:09
2014-01-01 21:23:33 Samil Vargas
why not PYTHON?
2013-12-17 02:15:53 Hector Monteo
Please, see my solution ID: 10678458

Last edit: 2013-12-17 02:15:59
2013-12-17 02:13:50 Hector Monteo
I need more test cases.
should print something for n = 10?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.