题目描述

圣诞节快到了，贴心的学生会为了增进同学间的感情，组织大家互相交换礼物。一共有n个班级参加了礼物交换活动，其中第i个班级有ai名学生，并准备了bi个礼物。
学生会希望尽可能多的学生能收到别的班级准备的礼物，因此规定每个人都只能收到一份礼物，并且每个人都只能收到别的班级准备的礼物。
学生会的同学还需要去组织联谊活动，因此拜托你来计算，在这样的规定下，最多有多少人能收到礼物。

输入

输入的第一行包含一个整数T，为询问的组数。
每组询问中，第一行为班级的个数n，第2到n+1行中，每行两个数，分别对应第1到第n个班级的学生数ai和礼物数bi。
1 <= T <= 100, 1 <= n <= 1e6, 0 <= ai, bi <= 1e9. 数据满足所有 n 之和不超过 2e6.

输出

输出T行，每行输出一个数，代表这一行对应的组的结果。

样例输入

2
2
2 3
4 5
3
5 1
6 1
7 1

样例输出

5
3