D. Cheater
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are playing a new card game in a casino with the following rules:

  1. The game uses a deck of $$$2n$$$ cards with different values.
  2. The deck is evenly split between the player and the dealer: each receives $$$n$$$ cards.
  3. Over $$$n$$$ rounds, the player and the dealer simultaneously play one top card from their hand. The cards are compared, and the point goes to the one whose card has a higher value. The winning card is removed from the game, while the losing card is returned to the hand and placed on top of the other cards in the hand of the player who played it.

Note that the game always lasts exactly $$$n$$$ rounds.

You have tracked the shuffling of the cards and know the order of the cards in the dealer's hand (from top to bottom). You want to maximize your score, so you can swap any two cards in your hand no more than once (to avoid raising suspicion).

Determine the maximum number of points you can achieve.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^{5}$$$) — the number of cards in the player's hand.

The second line of each test case contains $$$n$$$ integers $$$a_{1}, a_{2}, \ldots, a_{n}$$$ ($$$1 \leq a_{i} \leq 2n$$$) — the values of the cards in the player's hand from top to bottom.

The third line of each test case contains $$$n$$$ integers $$$b_{1}, b_{2}, \ldots, b_{n}$$$ ($$$1 \leq b_{i} \leq 2n$$$) — the values of the cards in the dealer's hand from top to bottom.

It is guaranteed that the values of all cards are distinct.

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

Output

For each test case, output a single integer — the maximum number of points you can achieve.

Example
Input
3
7
13 7 4 9 12 10 2
6 1 14 3 8 5 11
3
1 6 5
2 3 4
5
8 6 3 10 1
7 9 5 2 4
Output
6
2
3
Note

In the first test case, the cards can remain unchanged. The gameplay will be organized as follows:

  1. The cards with values $$$13$$$ and $$$6$$$ are compared. The player wins and receives a point.
  2. The cards with values $$$7$$$ and $$$6$$$ are compared. The player wins and receives a point.
  3. The cards with values $$$4$$$ and $$$6$$$ are compared. The dealer wins.
  4. The cards with values $$$4$$$ and $$$1$$$ are compared. The player wins and receives a point.
  5. The cards with values $$$9$$$ and $$$1$$$ are compared. The player wins and receives a point.
  6. The cards with values $$$12$$$ and $$$1$$$ are compared. The player wins and receives a point.
  7. The cards with values $$$10$$$ and $$$1$$$ are compared. The player wins and receives a point.
Thus, the player received $$$6$$$ points.

In the second test case, the cards with values $$$1$$$ and $$$5$$$ can be swapped, then the player's hand looks as follows $$$[5, 6, 1]$$$. The gameplay will be organized as follows:

  1. The cards with values $$$5$$$ and $$$2$$$ are compared. The player wins and receives a point.
  2. The cards with values $$$6$$$ and $$$2$$$ are compared. The player wins and receives a point.
  3. The cards with values $$$1$$$ and $$$2$$$ are compared. The dealer wins.
Thus, the player received $$$2$$$ points.

In the third test case, the cards with values $$$3$$$ and $$$10$$$ can be swapped, then the player's hand looks as follows $$$[8, 6, 10, 3, 1]$$$. The gameplay will be organized as follows:

  1. The cards with values $$$8$$$ and $$$7$$$ are compared. The player wins and receives a point.
  2. The cards with values $$$6$$$ and $$$7$$$ are compared. The dealer wins.
  3. The cards with values $$$6$$$ and $$$9$$$ are compared. The dealer wins.
  4. The cards with values $$$6$$$ and $$$5$$$ are compared. The player wins and receives a point.
  5. The cards with values $$$10$$$ and $$$5$$$ are compared. The player wins and receives a point.
Thus, the player received $$$3$$$ points.


close