Problem Description

Sunset and Elephant formed a programming contest team named ``Speed Dog''. There are $n$ problems in the online judge, labeled by $1,2,\dots,n$.

For the $i$-th problem, Sunset needs to code $a_i$ bytes while Elephant needs to code $b_i$ bytes. But they can work on problems together. Specifically, for the $i$-th problem, they can choose a real number $x_i(0\leq x_i\leq 1)$, split this problem into two parts $A$ and $B$, then assign Sunset to code part $A$ and assign Elephant to code part $B$. As a result, Sunset will code $a_i\times x_i$ bytes, and Elephant will code $b_i\times(1-x_i)$ bytes.

Now they want to solve all the problems whose labels are not larger than $k$. Assume Sunset codes $X$ bytes in total and Elephant codes $Y$ bytes in total. It is too tired for a coder to code too much code. Please help them find an assignment that $\max(X,Y)$ is minimized.

Input

The first line of the input contains an integer $T(1\leq T\leq 10000)$, denoting the number of test cases.

In each test case, there is one integer $n(1\leq n\leq 250000)$ in the first line, denoting the number of problems.

For the next $n$ lines, each line contains two integers $a_i,b_i(1\leq a_i,b_i\leq 1000)$, denoting each problem.

It is guaranteed that $\sum n\leq 10^6$.

Output

For each test case, print $n$ lines in format $\texttt{u/v}$, where the $i$-th line denotes the minimum value of $\max(X,Y)$ when $k=i$. Note that you should guarantee that $\gcd(u,v)=1$.

1
3
1 3
3 1
2 2

3/4
1/1
2/1