Background

Problem D. I do not want to be hacked!!!

Problem Description

There are $n+2$ points in a line, numbered $0\sim n+1$. For point $i$, there are two integers $a_i, b_i$, where $0\le i\le n+1$. Initially, define $a_0=b_0=a_{n+1}=b_{n+1}=0$.

Suppose you are currently at point $x$, and the current moving direction is $y$. Initially, $x=0, y=1$.

You will move in the following way until after some change of $x, y$ you get $x=0, y=-1$ or $x=n+1, y=1$.

• If $y=1$, first increase $x$ by $1$. Then if $a_x>0$, set $y$ to $-1$; otherwise, keep $y$ unchanged. Finally, decrease $a_x$ by $1$.
• If $y=-1$, first decrease $x$ by $1$. Then if $b_x>0$, set $y$ to $1$; otherwise, keep $y$ unchanged. Finally, decrease $b_x$ by $1$.

Ask which point number $x$ will be at when the process ends. In fact, in the end, $x$ can only be at point $0$ or point $n+1$.

Input Format

This problem has multiple sets of testdata. The first line contains a positive integer $T$, the number of test cases, followed by $T$ test cases.

For each test case, the first line contains a positive integer $n$.

Then follow $n$ lines, each containing two non-negative integers $a_i, b_i$, representing the initial values of $a_i, b_i$.

Output Format

For each test case, output one line with one integer, indicating which point number $x$ will be at when the process ends.

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

0
4
0

Hint

Sample Explanation

For the $1$st sample test case, $(x,y)$ changes as $(0,1)\to (1,1)\to (1,-1)\to (0,-1)$.

For the $2$nd sample test case, $(x,y)$ changes as $(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)$.

For the $3$rd sample test case, $(x,y)$ changes as $(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)$.

Constraints and Notes

For the first $30\%$ of the test points, it is guaranteed that $n,a_i,b_i\le 10$.

For the first $60\%$ of the test points, it is guaranteed that $\sum n\le 5000$.

For the other $20\%$ of the test points, it is guaranteed that $T=10$, $n=10^5$, and $a_i,b_i$ are generated uniformly at random within the specified range. In particular, it is guaranteed that for all test points except this part, $T\ne 10$.

For all test points, it is guaranteed that $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$.

Translated by ChatGPT 5