J. Arranged Marriage
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

In Nlogonia city there are $$$n$$$ families,the $$$i_{ith}$$$ family has $$$b_i$$$ boys and $$$g_i$$$ girls.

For two integers $$$l$$$ and $$$r$$$ $$$(1 \le l \le r \le n)$$$ when we consider families in the range $$$[l,r]$$$, if it is possible to arrange all the boys and girls whose families are in the given range in couples, then the range $$$[l,r]$$$ is good.

Note that each boy in the given range can marry any girl from the given range,but he can't marry a girl from his family.

Your task is to count the number of good ranges.

Input

The first line contains a single integer $$$t$$$ $$$(1 \le t \le 3 \times 10^5)$$$, the number of test cases.

The first line of each test case contains an integer $$$n$$$ $$$(1 \le n \le 3 \times 10^5)$$$, the number of families.

The second line of each test case contains $$$n$$$ integers $$$b_i$$$ $$$(1 \le b_i \le 10^9)$$$, the number of boys in each family.

The third line of each test case contains $$$n$$$ integers $$$g_i$$$ $$$(1 \le g_i \le 10^9)$$$, the number of girls in each family.

It is guaranteed that the sum of $$$n$$$ overall test cases doesn't exceed $$$3 \times 10^5$$$.

Output

For each query in each test case print the number of good ranges.

Example
Input
5
3
2 2 2
1 1 4
4
1 2 2 5
2 1 3 4
4
3 2 2 1
3 1 1 3
5
2 1 2 3 1
1 2 1 1 3
5
2 3 1 2 3
3 3 2 3 2
Output
1
2
2
4
1