#2398 세쌍둥이 쎅시 소수(sexy prime triplets)

21  1 s   128 MB  

Description

세쌍둥이 쎅시 소수(sexy prime triplets)란 $n,  n+6,  n+12$가 모두 소수가 될 때 세 소수를 의미한다.

(‘쎅시(sexy)’란 여섯(6)을 의미하는 라틴어 ‘sex’에서 유래되었다).

$1$ 이상의 정수가 $2$개 주어질 경우 두 값 사이에 존재하는 세쌍둥이 쎅시 소수의 값들을 출력하는 프로그램을 작성하시오.

Input

테스트케이스 개수 $T$($1 \leq T \leq 10$ 인 정수)가 첫 줄에 입력된다.

그 다음 줄부터 $2$개의 정수 $m, n$($1 \leq m, n \leq 5,000,000$)이 한 줄씩 $T$ 개수만큼 입력된다.

Output

각 입력에 대하여 $m$과 $n$사이에 존재($m, n$ 포함)하는 세 쌍둥이 쎅시 소수 $3$개를 오름차순으로

한 줄에 한 결과씩 출력하되 순서대로 번호를 매기고 숫자들 사이에는 ‘-' 기호를 넣으시오

(*자세한 형식은 sample output을 참조하시오)

만약 주어진 두 정수 사이에 세쌍둥이 쎅시 소수가 하나도 존재하지 않는 경우에는

“No Sexy Prime Triplets!” 라고만 출력한다(각 테스트케이스들의 출력 결과들 사이에는 빈 줄을 넣지 마시오).

Sample Input

Sample Output

2
1 50
1000 1100
1: 5-11-17
2: 7-13-19
3: 11-17-23
4: 17-23-29
5: 31-37-43
No Sexy Prime Triplets!

Source

동의대학교 멀티미디공학과 우영운(2015년 4월 23일)