최소 서로소 구간

오늘 Little John은 저축한 돈을 모두 털어 구간 하나를 샀다. 그는 이 구간 위에 집을 짓고 싶어 한다.

양의 정수로 이루어진 구간 $[l,r]$에서 $l$과 $r$이 서로소이면 이 구간을 서로소 구간이라고 한다. 서로소 구간 $[l,r]$이 자신 외에 다른 서로소 구간을 포함하지 않으면 이 구간을 최소 서로소 구간이라고 한다. 자세한 내용은 아래 설명을 참고한다.

양의 정수로 이루어진 구간 $[l,r]$이 주어질 때, $[l,r]$에 포함된 최소 서로소 구간의 개수를 구하라.

두 정수 $a$와 $b$는 공통된 양의 약수가 $1$뿐일 때 서로소이다. 예를 들어 $2$와 $4$는 둘 다 $2$로 나누어지므로 서로소가 아니다. 반면 $7$과 $9$는 공통 약수가 $1$뿐이므로 서로소이다.

구간 $[l',r']$이 $[l,r]$에 포함된다는 것은 $l \le l' \le r' \le r$이 성립한다는 뜻이다.

첫 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 100$)가 주어진다. 각 테스트 케이스는 한 줄이며, 정수 $l$과 $r$ ($1 \le l \le r \le 10^9$)이 주어진다.

각 테스트 케이스마다 $[l,r]$에 포함된 최소 서로소 구간의 개수를 한 줄에 하나씩 출력한다.

첫 번째 테스트 케이스의 구간은 $[1,2]$이다. 구간 $[1,1]$은 $1$과 $1$이 서로소이고 다른 구간을 포함하지 않으므로 최소 서로소 구간이다. 구간 $[1,2]$도 서로소 구간이지만 $[1,1]$을 포함하므로 최소 서로소 구간이 아니다. 구간 $[2,2]$는 $2$와 $2$의 공약수가 $1$과 $2$이므로 서로소가 아니다. 따라서 $[1,2]$에 포함된 최소 서로소 구간은 1개이다.