题目背景

D题，我不要被hack！！！

题目描述

有 $n+2$ 个点排成一排，编号为 $0\sim n+1$。对于第 $i$ 号点有两个整数 $a_i,b_i$，其中 $0\le i\le n+1$。规定初始时 $a_0=b_0=a_{n+1}=b_{n+1}=0$。

设你当前在第 $x$ 号点，当前的移动方向为 $y$，初始时 $x=0,y=1$。

你将按如下方式移动直到 $x,y$ 某一次变化后满足 $x=0,y=-1$ 或 $x=n+1,y=1$。

• 若 $y=1$，首先将 $x$ 增加 $1$，此时若 $a_x>0$ 则将 $y$ 变成 $-1$，否则 $y$ 不变，最后再将 $a_x$ 减少 $1$。
• 若 $y=-1$，首先将 $x$ 减少 $1$，此时若 $b_x>0$ 则将 $y$ 变成 $1$，否则 $y$ 不变，最后再将 $b_x$ 减少 $1$。

问最后结束时 $x$ 会在第几号点，事实上，最后 $x$ 仅可能在第 $0$ 号点或第 $n+1$ 号点。

输入格式

本题有多组测试数据。第一行输入一个正整数 $T$，表示测试数据组数，接下来分别输入 $T$ 组数据。

对于每组测试数据，第一行输入一个正整数 $n$。

接下来 $n$ 行每行输入两个非负整数 $a_i,b_i$，表示 $a_i,b_i$ 的初始值。

输出格式

对于每组测试数据输出一行一个整数表示最后结束时 $x$ 会在第几号点。

3
1
1 1
3
0 1
1 1
1 0
3
0 1
2 3
4 5

0
4
0

提示

样例解释

对于样例第 $1$ 组数据，$(x,y)$ 依次为 $(0,1)\to (1,1)\to (1,-1)\to (0,-1)$。

对于样例第 $2$ 组数据，$(x,y)$ 依次为 $(0,1)\to (1,1)\to (2,1)\to (2,-1)\to (1,-1)\to (1,1)\to (2,1)\to (3,1)\to (3,-1)\to (2,-1)\to (2,1)\to (3,1)\to (4,1)$。

对于样例第 $3$ 组数据，$(x,y)$ 依次为 $(0,1)\to (1,1)\to (2,1)\to (2,-1)\to (1,-1)\to (1,1)\to (2,1)\to (2,-1)\to (1,-1)\to (0,-1)$。

数据范围与约定

对于前 $30\%$ 的测试点，保证 $n,a_i,b_i\le 10$。

对于前 $60\%$ 的测试点，保证 $\sum n\le 5000$。

对于另外 $20\%$ 的测试点，保证 $T=10$，$n=10^5$，$a_i,b_i$ 在指定范围内均匀随机生成。特别的，保证除该档部分分外所有测试点满足 $T\ne 10$。

对于所有测试点，保证 $1\le T\le 10^4$，$1\le n\le 10^5$，$1\le \sum n\le 10^6$，$0\le a_i,b_i\le 10^6$。