Expected value of the greatest common divisor

Each of K values is chosen uniformly from its own interval; find the expected gcd of the K chosen numbers as a fraction mod 1e9+7.

Hard9ProbabilityMathNumber theoryDynamic programmingNo attempts yetTime limit2sMemory limit512 MB

Description

Examples2

Problem

You are given two sequences $A$ and $B$ of length $K$ . A sequence $X$ is built from $A$ and $B$ : each $X_i$ is an integer picked uniformly at random from the integers between $A_i$ and $B_i$ , inclusive, and every $X_i$ is picked independently.

Given $A$ and $B$ , write a program that computes the expected value of $\gcd(X_0, X_1, \dots, X_{K-1})$ .

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 50$ ).

The first line of each test case contains $K$ ( $2 \le K \le 5$ ). Each of the next $K$ lines contains $A_i$ and $B_i$ , separated by a space. ( $1 \le A_i \le B_i \le 200000$ )

Output

For each test case, print one answer on its own line.

Write the expected value as an irreducible fraction $P/Q$ . Print $N$ ( $0 \le N \le 10^9+6$ ) such that $P + Q \times N$ is divisible by $10^9+7$ . If no such $N$ exists, print $-1$ .