양 세기

양 Bleatrix Trotter는 더 빨리 잠드는 데 도움이 되는 전략을 고안했다. 먼저 수 N을 고른다. 그런 다음 N, 2 × N, 3 × N 등을 차례로 말하기 시작한다. 수를 말할 때마다 그 수의 모든 자릿값을 생각한다. 지금까지 자신이 말한 수 중 하나의 일부로 적어도 한 번 본 숫자들(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)을 기록한다. 열 개의 숫자를 각각 적어도 한 번 본 순간 잠든다.

Bleatrix는 반드시 N부터 시작해야 하며, i × N을 말한 직후에는 항상 (i + 1) × N을 말해야 한다. 예를 들어 Bleatrix가 N = 1692을 골랐다고 하자. 다음과 같이 센다.

• N = 1692. 이제 숫자 1, 2, 6, 9을 보았다.

• 2N = 3384. 이제 숫자 1, 2, 3, 4, 6, 8, 9을 보았다.

• 3N = 5076. 이제 열 개의 숫자를 모두 보았으므로 잠든다.

잠들기 전에 마지막으로 말할 수는 무엇인가? 영원히 세게 된다면 대신 INSOMNIA을 출력한다.

제한

테스트 세트당 시간 제한: 20초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100.

작은 데이터 세트(테스트 세트 1 - 공개)

0 ≤ N ≤ 200.

큰 데이터 세트(테스트 세트 2 - 비공개)

0 ≤ N ≤ $10^{6}$.

입력의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 Bleatrix가 고른 수인 정수 N 하나가 있는 한 줄로 구성된다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호(1부터 시작)이고, y은 문제 설명에 기술된 규칙에 따라 Bleatrix가 잠들기 전에 마지막으로 말할 수이다.

케이스 #1에서는 2 × 0 = 0, 3 × 0 = 0 등과 같이 이어지므로, Bleatrix는 0 이외의 숫자를 절대 보지 못한다. 따라서 영원히 세며 결코 잠들지 못한다. 불쌍한 양이다!

케이스 #2에서 Bleatrix는 1, 2, 3, 4, 5, 6, 7, 8, 9, 10을 말한다. 0은 마지막으로 필요한 숫자이므로, 10을 말한 뒤 잠든다.

케이스 #3에서 Bleatrix는 2, 4, 6... 등을 차례로 말한다. 90을 말할 때까지 어느 수에서도 숫자 9을 보지 못하며, 그 시점에 잠든다. 그때까지 숫자 0, 1, 2, 3, 4, 5, 6, 7, 8을 이미 보았으며, 이들은 각각 수 10, 10, 2, 30, 4, 50, 6, 70, 8에서 처음 등장했다.

케이스 #4에서 Bleatrix는 11, 22, 33, 44, 55, 66, 77, 88, 99, 110을 말한 뒤 잠든다.

케이스 #5은 문제 설명에서 다룬 경우이다. 이 케이스는 큰 데이터 세트에만 등장하며 작은 데이터 세트에는 등장하지 않는다는 점에 유의하라.