Sunset and Elephant formed a programming contest team named ``Speed Dog''. There are nn problems in the online judge, labeled by 1,2,…,n1,2,…,n.
For the ii-th problem, Sunset needs to code aiai bytes while Elephant needs to code bibibytes. But they can work on problems together. Specifically, for the ii-th problem, they can choose a real number xi(0≤xi≤1)xi(0≤xi≤1), split this problem into two parts AAand BB, then assign Sunset to code part AA and assign Elephant to code part BB. As a result, Sunset will code ai×xiai×xi bytes, and Elephant will code bi×(1−xi)bi×(1−xi) bytes.
Now they want to solve all the problems whose labels are not larger than kk. Assume Sunset codes XX bytes in total and Elephant codes YY 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)max(X,Y) is minimized.
Input
The first line of the input contains an integer T(1≤T≤10000)T(1≤T≤10000), denoting the number of test cases.
In each test case, there is one integer n(1≤n≤250000)n(1≤n≤250000) in the first line, denoting the number of problems.
For the next nn lines, each line contains two integers ai,bi(1≤ai,bi≤1000)ai,bi(1≤ai,bi≤1000), denoting each problem.
It is guaranteed that ∑n≤106∑n≤106.
Output
For each test case, print nn lines in format u/vu/v, where the ii-th line denotes the minimum value of max(X,Y)max(X,Y) when k=ik=i. Note that you should guarantee that gcd(u,v)=1gcd(u,v)=1.