#2144 수소(emirp)

31  1 s   128 MB  

Description

수소(emirp)란 소수(prime number)를 거꾸로 읽었을 때도 소수가 되는 수를 수소라고 한다. 그러나 앞으로 읽으나 거꾸로 읽으나 동일한 수는 수소에 포함하지 않는다. 1 이상의 정수가 2개 M과 N이 주어질 경우 [M, N] 범위에 존재하는 가장 큰 수소, 가장 작은 수소, 그리고 수소의 개수를 출력하는 프로그램을 작성하시오.

Input

테스트 케이스의 수 T가 들어온다. (1 <= T <= 10) 그 다음 T만큼 정수 M, N이 한 줄에 한 쌍씩 들어온다. (1 <= M, N <= 100,000)

Output

각 테스트 케이스마다 [M, N] 범위에 존재하는 가장 큰 수소, 가장 작은 수소, 수소의 개수를 한 칸씩 띄어 한 줄씩 출력한다. 만약 해당 구간에 수소가 하나도 존재하지 않을 경우에는 모두 0을 출력하도록 한다.

Sample Input

Sample Output

2
1 50
100 1000
37 13 4
991 107 28

Source

동의대학교 멀티미디공학과 우영운(2014년 5월 15일)