有n只小怪物首尾相连围成一个环形，从某个小怪物开始，我们将其编号为1,2,3,...,n；第i只小怪物都有耐水力a_i和爆炸力b_i。

每当你用小水枪滋一下某只小怪物，它的耐水力就会-1，当某只小怪物的耐水力降低到0或更低时，它就会倒下并爆出若干水其中一部分水会滋到后面的怪物身上从而造成b_i的伤害，即第i+1只小怪物在第i只小怪物倒下时会降低b_i的耐水值。

那么，你最少需要共用小水枪滋多少下小怪物才能让所有的小怪物都会倒下呢？

注意，无论你如何滋一只已经倒下的小怪物它都不会再爆了。

第一行，一个正整数t，表示测试组数。

每组测试数据的第一行，一个正整数n，表示小怪物个数。

每组测试数据接下来的n行，按从1到n的顺序依次给出两个整数a_i,b_i，分别表示第i只小怪物的耐水值和排水值。

对于100%的数据：

1 \le t \le 100000 ；

1 \le n \le 100000 ；

1 \le t×n \le 10^6；

1 \le a_i,b_i \le 10^{12} 。

每组测试数据一个数字，表示最少需要滋多少下。

注意：输入量较大，用scanf,printf或cin.tie(0)。