wbyblD

有 $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$ 号点。 ## Input 本题有多组测试数据。第一行输入一个正整数 $T$，表示测试数据组数，接下来分别输入 $T$ 组数据。 对于每组测试数据，第一行输入一个正整数 $n$。 接下来 $n$ 行每行输入两个非负整数 $a_i,b_i$，表示 $a_i,b_i$ 的初始值。 ## Output 对于每组测试数据输出一行一个整数表示最后结束时 $x$ 会在第几号点。 [samples] ## Background > D题，我不要被hack！！！ ## Note #### 样例解释 对于样例第 $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$。