YYJ has many magic beads with two colors, red and blue. If a red bead is on the left of a blue bead and they are next to each other, they will disappear and release 1 unit of magic power. YYJ has \(n\) strings of beads, each string is consists of \(a_i\) blue beads on the left and \(b_i\) red beads on the right (To make sure they will disappear). Note that \(a_i\)and \(b_i\) can be zero.
YYJ now wants to connect these strings in some order and she is wondering how many units of magic power she can get at most.
The first line contains an integer \(T\), indicating the number of test cases. For each test case:
The first line contains an integer \(n(1\le n\le 100\ 000)\), indicating the number of string of beads.
Each of the next \(n\) lines contains two integers \(a_i, b_i(1\le a_i+b_i\le10\ 000)\).
It is guaranteed that \(\sum (a_i+b_i)\le500\ 000\).
Output one integer, indicating the answer.
We use 'R' to denote red beads and 'B' to denote blue beads.
We have 2 strings: BRR, BBR at first.
The string after connection is: BRRBBR, which can gain 2 units of magic power.