만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

빠진 숫자

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

요약
a부터 b까지의 정수를 이어 붙인 문자열에서 수 하나가 빠졌을 때, 빠졌을 수 있는 모든 수를 구합니다.
난이도

어려움10점 중 8점

유형
문자열, 구현, 수학
정답자
아직 제출이 없습니다

문제

키르비는 aa부터 bb까지의 모든 정수를 순서대로 적었다. 공백 없이, 앞자리 0 없이 이어 붙여 하나의 긴 문자열로 만들었다. 그러나 aa와 bb의 값은 알려 주지 않았다.

키르비가 배가 고파서 적힌 숫자 중 하나를 먹어 버렸다. 그가 먹은 숫자가 무엇인지 알아낼 수 있는가?

입력

첫 줄에 테스트 케이스의 개수를 나타내는 정수 tt (1≤t≤1051 \le t \le 10^5)가 주어진다.

이어지는 tt개의 줄에는 길이가 1 이상 488888 이하인 숫자 문자열이 각각 주어진다. 이는 키르비가 적은 문자열이다. 1≤a<b≤999991 \le a < b \le 99999이며, 이 문자열은 위의 과정으로 만들어질 수 있음이 보장된다.

모든 문자열 길이의 합은 10610^6을 넘지 않는다.

출력

테스트 케이스마다 두 줄을 출력한다.

첫 줄에는 키르비가 먹었을 수 있는 숫자의 개수를 출력한다.

둘째 줄에는 그 숫자들을 오름차순으로, 하나 이상의 공백으로 구분하여 출력한다.

예제1

  1. 예제 1

    입력
    1
    891112
    
    예상 출력
    1
    10