시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 126 85 78 81.250%

문제

블리트릭스라는 양은 더 빨리 잠을 들기 위한 전략을 세웠다.

먼저, 숫자 N을 뽑는다. 그리고 N, 2 × N, 3 × N 등을 떠올린다. 숫자를 떠올릴 때 마다, 그 숫자의 모든 자리수의 숫자들을 적어놓는데, 이미 적은 숫자는 또 적지 않는다. 0에서 9까지의 모든 숫자가 적히게 되면 잠이 든다.

블리트릭스는 N에서 시작해서 i × N 후에는 (i + 1) × N을 떠올리게 된다. 예를 들어 N = 1692 일 경우, 다음 과 같이 진행된다:

  • N = 1692. 1, 2, 6, 9가 기록된다.
  • 2N = 3384. 1, 2, 3, 4, 6, 8, 9가 기록된다.
  • 3N = 5076. 모든 수가 기록되고, 잠에 빠진다.

블리트릭스가 잠에 빠지는 수는 무엇인가? 영원히 잠에 들 수 없다면 INSOMNIA라고 출력하라.

입력

첫번째 행은 케이스의 개수, T이다. 다음 행부터는 T개의 케이스들이 나온다. 각 케이스는 블리트릭스가 고른 하나의 숫자 N으로 구성된다.

제한

  • 1 ≤ T ≤ 100.
  • 0 ≤ N ≤ 200.

출력

각 케이스에 대해서, 케이스 번호가 x이고 y가 정답일 때, Case #x: y라고 출력해야 한다.

예제 입력

5
0
1
2
11
1692

예제 출력

Case #1: INSOMNIA
Case #2: 10
Case #3: 90
Case #4: 110
Case #5: 5076

힌트

예제 입출력 1번에 대해서, 2 × 0 = 0, 3 × 0 = 0 등등으로 이어지므로, 블리트릭스는 0외에는 다른 숫자를 기록할 수 없을 것이며, 따라서 영원히 잠에 들 수 없다.

예제 입출력 2번의 경우, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 순으로 떠올릴 것이며, 0이 가장 마지막에 기록되는 수가 될 것이다. 따라서 10이 마지막 수가 될 것이다.

예제 입출력 3번의 경우, 2, 4, 6... 등등으로 떠올릴 것이다. 숫자 9는 90 전에는 기록할 수 없다. 90을 떠올렸을 때 이미 블리트릭스는 0~8의 숫자를 적었을 것이므로, 90이 마지막 수가 될 것이다.

예제 입출력 4번은 블리트릭스가 11, 22, 33, 44, 55, 66, 77, 88, 99, 110 을 떠올릴 것이고, 110이 마지막 수가 될 것이다.

예제 입출력 5번은 문제에서 설명한 수이다.