Missing Number

시간 제한2초메모리 제한2048 MB

요약

a부터 b까지의 연속한 정수를 이어 붙인 뒤 한 수를 지운 문자열이 주어질 때, 지워졌을 수 있는 모든 수를 찾는다.

난이도: 어려움10점 중 8점
유형: 문자열, 구현, 완전 탐색, 수학
정답자: 아직 제출이 없습니다

문제

Kirby has written down all the integers from $a$ to $b$ in order. He wrote them down as one big string, with no spaces between them and no leading zeroes, and he didn't tell you the values of $a$ and $b$ !

Because Kirby was hungry, he ate one of the numbers. Can you figure out what number he ate?

입력

The first line contains a single integer $t$ ( $1 \le t \le 10^5$ ), which is the number of test cases that follow.

Each of the next $t$ lines contains a string of digits of length at least one and at most $488888$ . This string is what Kirby wrote. Note that $1 \le a < b \le 99999$ . It is guaranteed that this string can be obtained by the process given above.

It is guaranteed that the sum of the lengths of all the strings does not exceed $10^6$ .

출력

Output $2t$ lines, two for each test case.

On the first line, output a single integer, which is the number of numbers that Kirby could have possibly eaten.

On the second line, output the numbers that Kirby could have eaten, in ascending order, separated by at least one space.

예제1

예제 1
입력
```
1
891112
```
예상 출력
```
1
10
```