The first day Mr.Cai met TT, He flipped. It was those eyes, something in those dazzling eyes. The next thing he know, he wanted holding her hand and looking right into her eyes. And He realized one thing: He had flipped. Completely.

The Mr.Cai begin to imagine a better life with TT.
Beacause TT is the one of the NBUT ACM trainning team members.
Mr.Cai want to start learning the new algorithm to teach the TT.

Mr.Cai learn N new algorithms to teach TT.
For each algorithm, Mr.Cai need t1 hours to explain, after Mr.Cai's explain, and TT need t2 hours to completely realize the new algorithm.
And TT is pretty smart. While Mr.Cai teaching TT the next new algorithm, TT can continue realize previously taught algorithms at the same time.

Mr.Cai want TT realize all the algorithm as quickly as possible.

There are T (T <= 20) test cases.
For each test case:
First line contain one integer N (0 < N <= 10000).
The follow N lines contain two integers t1 and t2 (0 < t1, t2 <= 1000).

For each test case, print the minimum time the TT realize all the algorithm.