34558번 - Prime Median

문제

$N$개의 닫힌구간 $[a_1,b_1],[a_2,b_2],\dots,[a_N,b_N]$이 주어집니다. 각 닫힌구간에서 존재하는 소수 중 중앙값을 출력하는 프로그램을 작성해 주세요.

만약, 닫힌구간 $[a_i,b_i]$에 소수가 존재하지 않거나 소수의 개수가 짝수인 경우 -1을 출력합니다.

입력

첫 줄에는 정수 $N$가 주어집니다. (1ドル \leq N \leq 100,000円$)

이후 $N$개의 줄에는 $a_i, b_i$가 주어집니다. (2ドル \leq a_i \leq b_i \leq 10^{6}, a_i, b_i$는 모두 정수입니다.)

출력

$i$번 줄에 $i$번째 구간에 대한 답을 출력합니다. 만약, $i$번째 구간 내에 소수가 존재하지 않거나 소수의 개수가 짝수일 경우, -1을 출력합니다.

제한

노트

닫힌구간 $[a_i,b_i]$는 $a_i,ドル $b_i$를 포함하는 구간입니다.