Problem 1988: scmax

You are given an array of integers. Find the longest increasing subsequence. Formally, remove as few values as possible such that the remaining values form a strictly increasing subsequence, and print the remaining numbers.

Just kidding, who needs this in real life? We are interested in something deeper than that.

Each number $a$ has now a favorite value $T_a$ , which even though it can be (according to the normal rules) $T_a \leq a$ , $a$ is ready to consider that $a < T_a$ , if this would bring $T_a$ immediately to the right of $a$ in the increasing subsequence we consider. As a consequence, alongside the normal comparison rules, we also introduce the relation $a < T_a$ , without deleting $T_a < a$ .

Task

Find the longest increasing subsequence, given the new conditions.

Formally, an array is now strictly increasing if for each pair of consecutive values $(L, R)$ , either $L < R$ or $T_L = R$ .

Input data

The first line contains the number $Q$ of tests in the file. For each test, the description is similar: On the first line, the number $N$ of numbers in the array. On the next line there are $N$ numbers with values between $1$ and $N$ , representing the array. On the next line there are $N$ numbers with values between $1$ and $N$ , the $i^{th}$ of which is $T_i$ .

Output data

The first line of each test case will contain the size of the longest maximally increasing substring of the string, considering new rules.

Constraints and clarifications

$1 \leq Q \leq 5$
$1 \leq N \leq 50 \ 000$
For $10$ points, $N \leq 14$
For $10$ other points, $N \leq 100$
For $10$ other points, $T_i = i$ , $\forall i$
For $10$ other points, all values from the array are $1$ , $2$ or $3$ .
For $10$ other points, for every integer $a$ there are at most $3$ values of $b$ such that $T_b = a$ .

Example

stdin

2
10
4 1 6 1 8 10 10 1 9 1
3 6 3 2 1 9 8 1 5 10
8
8 1 8 6 4 8 5 7
7 3 2 8 8 4 5 6

stdout

5
6

Explanation

In the first test, the maximum sequence is $4 \ 6 \ 8 \ 10 \ 10$
In the second test, the maximum sequence is $1 \ 8 \ 6 \ 4 \ 5 \ 7$

scmax