Champernowne 부분 문자열

Champernowne 문자열은 양의 정수를 순서대로 10진법 표기로 이어 붙여 만든 무한 문자열이다. 시작 부분은 1234567891011121314...이다. 임의의 유한한 숫자열은 이 문자열의 부분 문자열로 적어도 한 번 나타남이 증명되어 있다.

숫자와 물음표(?)로 이루어진 문자열이 주어진다. 각 물음표를 0부터 9까지의 숫자 하나로 바꿨을 때, 그 문자열이 Champernowne 문자열의 부분 문자열로 나타나는 가장 작은 인덱스를 구하라. 각 물음표는 서로 다른 숫자로 바꿀 수 있다. 인덱스는 클 수 있으므로 $998\\,244\\,353$으로 나눈 나머지를 출력한다.

첫 줄에 테스트 케이스의 수 $t$ $(1 \leq t \leq 10)$가 주어진다. 이어지는 $t$개의 줄에는 각각 숫자 0부터 9까지와 물음표로 이루어진 문자열 $s$ $(1 \leq |s| \leq 25)$가 주어진다.

각 테스트 케이스마다 가장 작은 인덱스를 $998\\,244\\,353$으로 나눈 나머지를 한 줄에 출력한다.