You are given $Q$ pairs of integers, the $i$-th pair being $a_i, b_i$. Determine $\frac{b_i}{a_i}$ modulo $M = 10^9 + 7$. Formally, find $x_i$ so that $$a_i \times x_i \equiv b_i \ (\text{mod } M)$$ where $$0 \le x_i \lt M$$ for each $1 \le i \le Q$.

Input

The first line consists of an integer $Q$.
Then, $Q$ lines follow, each line consists of two integers $a_i, b_i$.

Output

Output $Q$ lines.
In the $i$-th line, output the answer for the $i$-th pair as an integer.

Constraints

For all testcases: $1 \le Q \le 10^6, 0 \le a_i, b_i \lt M$
Subtask 1 (50%): $Q = 1$
Subtask 2 (50%): No other constraints

Hint

$\frac{1}{a} \equiv a^{M-2} \ (\text{mod } M)$.