#P2396. 调皮的CTX学长

调皮的CTX学长

       一天,C学长和Z学长去海边捡了很多贝壳,C学长捡了a个贝壳,Z学长捡了b个贝壳。(a>=b)Z学长看到自己的贝壳不比C学长的多,于是就很不高兴,然后就把C学长的贝壳扔了,但是Z学长也是有原则的人,每次只扔(与现在自己手里拿的贝壳一样多的)数量,如果扔完之后还是不高兴,那么就会继续扔,直到高兴为止。

    (例如Z学长手里现在手里有3个,C学长手里有7个,那么Z学长就会扔掉C学长手里的3个贝壳,然后Z学长还不高兴,就再次扔掉3个,最后C学长就剩下了1个)。

      如果C学长的贝壳数量小于Z学长的,那么C学长就会不高兴,C学长会直接夺走Z学长手中所有的贝壳,并把自己的贝壳给Z学长,(例如C学长有1个贝壳,而Z学长有3个,那么C学长就把Z学长的3个贝壳夺走,并把自己的1个贝壳给Z学长)。

经过多次的扔贝壳和夺贝壳,最终Z学长wa的一声哭了,原因是Z学长手中没有贝壳了,无法在扔掉C学长的贝壳,Z学长最后不知道C学长还有多少贝壳,请你设计一个程序计算出C学长最后手中的贝壳的数量。

Input

第一行输入一个数n(n<10000),接下来n行每行有两个数a,b(100000000>=a>=b>0)。

Output

C学长手中的贝壳个数

Sample Input

3
7 3
102 57
100000000 1

Sample Output

1
3
1

HINT

Source