보다 큰 정수 중 양의 약수가 과 자기 자신뿐인 수를 소수라고 하고, 소수가 아닌 수를 합성수라고 한다. 은 소수도 합성수도 아니다.
수열 와 를 다음과 같이 정의한다.
의 첫 다섯 항은 이고, 의 첫 다섯 항은 이다.
의 첫 개 항 뒤에 의 첫 개 항을 이어 붙여 길이가 인 수열 를 만든다. 즉,
이다.
에서 번째로 작은 수를 구하여라. 단, 정답이 클 수 있으므로 그 수를 으로 나눈 나머지를 출력한다.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 에서 번째로 작은 수를 으로 나눈 나머지를 한 줄에 출력한다. 테스트 케이스가 입력된 순서대로 출력한다.
첫 번째 테스트 케이스에서 이므로 첫 번째로 작은 수는 이다.
두 번째 테스트 케이스에서 이다. 이를 오름차순으로 정렬하면 이므로 세 번째로 작은 수는 이다.
첫째 줄에 테스트 케이스의 개수 가 주어진다. 각 테스트 케이스는 다음과 같은 형식으로 주어진다.
한 줄에 두 정수 과 가 공백으로 구분되어 주어진다.
세 번째 테스트 케이스에서 이다. 이를 오름차순으로 정렬하면 이므로 두 번째로 작은 수는 이다.
