크기가 K인 두 수열 A와 B가 주어진다. 수열 X는 A와 B를 이용해서 만들 수 있으며, X_i는 A_i보다 크거나 같고, B_i보다 작거나 같은 정수 중에서 랜덤하게 고른다. </p>

수열 A와 B가 주어졌을 때, GCD(X₀, X₁, ..., X_K-1)의 기댓값을 구하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 50)가 주어진다.</p>

각 테스트 케이스의 첫째 줄에는 K (2 ≤ K ≤ 5)가 주어진다. 다음 K개의 줄에는 A_i와 B_i가 한 줄에 하나씩 주어진다. (1 ≤ A_i ≤ B_i ≤ 200000)

출력 형식

문제의 정답이 P/Q인 경우에, 10⁹+7로 나누어 떨어지는 P+Q×N을 찾고, 그 때 N (0 ≤ N ≤ 10⁹+6)을 첫째 줄에 출력한다. 만약, N이 존재하지 않으면 -1을 출력한다.

예제 입력

4
2
2 4
3 5
3
1 2
1 2
1 2
3
1 12
1 12
1 12
2
2700 2701
2612 2724

예제 출력

333333334
875000005
722222226
314159265