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$를 포함하는 구간입니다.