Find the S

After getting rejected by his crush for 7th time, Rakib decided to leave all these silly worldly things and sink into the ocean of books. For some reasons, he started to like the letter ‘S’ from then. Anyways, he has invited his $n-1$ friends on a party and arranged a weird contest. Each person (including Rakib) takes a book from his collection and sits in n chairs numbered serially from 1 to $n$. The $i$-th person (according to chair number) gets a book consisting of $y_i$ words and among them, $x_i$ words contain the letter ‘S’.

The game goes as follows. At each round, everyone randomly opens a page from his own book and then randomly chooses a word. If no one gets a word which contains ‘S’, the game goes to next round. Otherwise among all the persons who got a word containing ‘S’, the person with the minimum chair number is declared the winner and the game ends.

As you might suspect, everyone wants to know the probability of them winning the contest. Can you help them?

It can be shown that all the probabilities can be shown as $\frac{P}{Q}$ where $P$ and $Q$ are co-prime integers and $Q \not\equiv 0 \mod (10^9+7)$. Print the value of $P⋅Q^{-1} \mod (10^9+7)$ for each probability.

Input

The first line contains the number of test cases $t$ ($1 ≤ t ≤ 10$). Each test case begins with a line containing a single integer $n$ ($1 ≤ n ≤ 100000$), the number of people in the party (including Rakib). Each of the following $n$ lines contain two integers, $x_i$ and $y_i$ ($1 ≤ y_i ≤ 100000$, $1 ≤ x_i ≤ y_i$).

Output

For each case, output $n$ integers in a line separated by spaces. The $i$-th integer should be the probability of the $i$-th person winning the game as $P.Q^{-1} \mod (10^9+7)$, for $P$ and $Q$ defined above.

Sample

Input	Output
2 2 1 2 2 3 3 1 2 4 6 3 4	200000002 800000006 869565224 913043485 217391306

Let $P$ be a prime. It can be shown that for any integer $A$ ($1 ≤ A < P$), there exists a unique integer $B$ ($1 ≤ B < P$) such that $AB ≡ 1 \mod P$. This $B$ is called the modular inverse of $A$ with respect to $P$ and is also expressed as $A^{-1}$.

Fermat's Little Theorem: If $P$ is a prime and $A$ is an integer co-prime with $P$, then $A^{P-1} ≡ 1 \mod P$.