You have N subjects in a course and you are given following information about the subjects: Each subject has two integers $start$ and $end$ which represents the study time starting from $start[i]$ to $end[i]$ to each of the i^th subject(1 ≤ i ≤ N) .

There are no two distinct subjects X and Y such that $start[X] ≤ start[Y]$ and $end[Y] ≤ end[X]$, which means that there is no subject whose studying interval is completely present inside the other subject studying interval. You are required to write a program to assign each subject a new interval of time such that all the N new intervals are assigned according to the following rules:

1. No two new intervals, X and Y should intersect for $1 <=X <=N$ , $1<=Y<=N$ and X not equal to Y. It means, if interval X lies between A and B then no other new interval should lie in this range.
2. New interval is a sub interval of the later one which means that if interval X lies in range $A<=X<=B$ and if Y is new interval then it must also lie within this range only.
3. All new intervals are of equal length so that you can provide proper time to each subject.

Input Format :
First line contains number of test cases T.
Each test case in it's first line contains N — the number of subjects.
Each of the next N lines contains information about one of the subject's studying interval — two integer numbers $start$ and $end$.

Output Format :
Print the maximal possible length of an interval in an irreducible fraction $p/q$

Input Constraints :
$1 <= T <=10$
$1 <= N <=10^5$
$0 ≤ start[i] < end[i] ≤ 10^6$ for all i between 1 to N

Note
Data provided in the input file confirms to the conditions laid out in the problem statement that is there are no two distinct X and Y such that start[X] ≤ start[Y] and end[Y] ≤ end[X]. Also each interval can have maximum precision that can be computed.

.