최대공약수의 기댓값

크기가 $K$인 두 수열 $A$와 $B$가 주어진다. 수열 $X$는 $A$와 $B$로 만들며, $X_i$는 $A_i$ 이상 $B_i$ 이하인 정수 중 하나를 같은 확률로 뽑은 값이다. 각 $X_i$는 서로 독립으로 뽑는다.

수열 $A$와 $B$가 주어졌을 때, $\gcd(X_0, X_1, \dots, X_{K-1})$의 기댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 50$)가 주어진다.

각 테스트 케이스의 첫째 줄에는 $K$ ($2 \le K \le 5$)가 주어진다. 다음 $K$개의 줄에는 $A_i$와 $B_i$가 공백으로 구분되어 한 줄에 하나씩 주어진다. ($1 \le A_i \le B_i \le 200000$)

각 테스트 케이스마다 한 줄에 답을 하나씩 출력한다.

기댓값을 기약분수로 나타낸 결과가 $P/Q$일 때, $P + Q \times N$이 $10^9+7$로 나누어떨어지는 $N$ ($0 \le N \le 10^9+6$)을 출력한다. 그런 $N$이 없으면 $-1$을 출력한다.