D. Rafael Leão (Light Blue)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Leonardo and Raphael are chasing Shredder through a long underground sewer.

The sewer consists of $$$n$$$ chambers arranged in a straight line, numbered from $$$1$$$ to $$$n$$$ from left to right.

At the beginning, Shredder may be anywhere in the sewer. Leonardo blocks the left side at chamber $$$L = 1$$$, and Raphael blocks the right side at chamber $$$R = n$$$. Therefore, the possible area where Shredder can still be hiding is the segment $$$[L, R]$$$.

no comment.

The turtles want to shrink this segment as much as possible.

You are given four arrays $$$a$$$, $$$b$$$, $$$c$$$, and $$$d$$$.

For every chamber $$$i$$$, the following conditions hold:

$$$$$$c_i \ge a_i \ge i$$$$$$

and

$$$$$$d_i \le b_i \le i$$$$$$

The turtles can perform the following moves any number of times and in any order:

  • If Leonardo is currently at chamber $$$L$$$, he may move forward to chamber $$$a_L$$$.

    However, this move is only safe if Raphael is far enough to cover him. Formally, the move is allowed only if:

    $$$$$$R \ge c_L$$$$$$

    After the move, the left boundary becomes $$$L = a_L$$$.

  • If Raphael is currently at chamber $$$R$$$, he may move backward to chamber $$$b_R$$$.

    However, this move is only safe if Leonardo is far enough to cover him. Formally, the move is allowed only if:

    $$$$$$L \le d_R$$$$$$

    After the move, the right boundary becomes $$$R = b_R$$$.

The turtles may stop after any number of moves. Their goal is to minimize the size of the final possible hiding segment.

Find the minimum possible value of:

$$$$$$R - L + 1$$$$$$

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — denotes the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — denotes the number of chambers.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$i \le a_i \le n$$$) — denotes the target chamber Leo can move to from chamber $$$i$$$.

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le i$$$) — denotes the target chamber Raph can move to from chamber $$$i$$$.

The fourth line contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$a_i \le c_i \le n$$$) — denotes the minimum chamber position Raph must be at ($$$R \ge c_L$$$) for Leo to safely execute his move from chamber $$$L$$$.

The fifth line contains $$$n$$$ integers $$$d_1, d_2, \dots, d_n$$$ ($$$1 \le d_i \le b_i$$$) — denotes the maximum chamber position Leo can be at ($$$L \le d_R$$$) for Raph to safely execute his move from chamber $$$R$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer — the minimum possible size of the final segment where Shredder may still be hiding.

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