[2019 SCPC 2차 예선]
수학과 프로그래밍을 좋아하는 \(A\)와 \(B\) 두 사람이 다음과 같은 게임을 하고 있다.
둘은 각각 1 이상 30,000 미만의 수 하나를 고른다.
이 수를 가지고 점수를 계산하여 큰 쪽이 이기는 게임이다.
어떤 수의 점수는, 이 수부터 시작해서 한 자리를 골라 이 자리의 숫자를 지워서 소수를 만들고, 이 과정을 연속해서 최대로 많이 만들 수 있는 소수의 개수이다.
이 과정에는 입력받은 원래의 수도 포함된다.
예를 들어, 127은 자신이 소수이다. 만약 7을 지우면 12가 되고, 이는 소수가 아니다.
그러나, 7을 지우는 대신 2를 지워서 17, 다시 1을 지워서 7을 만들면 총 3개의 소수를 연속해서 만들 수 있으며, 127의 점수는 3, 즉 127에서 규칙을 지키면서 소수를 최대로 많이 만들 수 있는 경우라는 것을 쉽게 보일 수 있다.
어떤 숫자를 지우더라도 소수를 만들 수 없다면 종료한다.
\(A\)와 \(B\)가 제시한 수에서 규칙에 의해 소수의 수열을 만들었을 때, 더 높은 점수를 얻는 수를 제시한 쪽이 이긴다.
둘이 제시한 수의 점수가 같다면 무승부이다.
규칙상, 소수가 아닌 수를 낸다면 이 수를 낸 쪽이 지거나, 비기는 경우 두 가지만 가능하다.
예를 들어, 128을 냈다면 이 수는 소수가 아니므로 이 수의 점수는 0점이고, 상대방도 합성수를 낸다면 비기고, 그렇지 않다면 지게 된다.
또한, 1은 소수가 아니다. \(A\)와 \(B\)가 제시하는 수의 어느 자리에도 0이 들어 있지 않다.
즉, 107과 같은 수를 제시할 수 없다.
\(A\), \(B\)가 고른 두 수를 가지고 승패를 결정하는 프로그램을 작성하시오.
입력 파일에는 여러 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 \(T\) 가 주어지고,
이후 차례로 \(T\) 개의 테스트 케이스가 주어진다. \(( 1 \le T \le 20)\)
각 테스트 케이스의 첫 줄에는 두 정수 \(A, B (1 \le A, B < 30,000)\)이 주어지는데, 이는 각각 \(A\)와 \(B\)가 고른 수를 나타낸다.
각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,
각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 C는 테스트 케이스의 번호이다.
그 다음 줄에, 이 테스트 케이스에서 \(A\)가 이기면 1, \(B\)가 이기면 2, 무승부이면 3을 출력하여라.
| 입력 |
|---|
| 2 127 128 131 127 |
| 출력 |
|---|
| Case #1 1 Case #2 3 |