您正在赌场玩新的纸牌游戏,规则如下:
- 游戏使用一副具有不同值的 $$$2n$$$ 卡牌。
- 这副牌在玩家和庄家之间平分:每人收到 $$$n$$$ 牌。
- 在 $$$n$$$ 轮中,玩家和庄家同时打出手中的一张顶牌。比较卡片,得分较高的卡片。获胜的牌从游戏中移除,而失败的牌则返回手牌 并放置在其他卡片之上 在玩它的玩家的手中。
注意游戏总是持续 正是 $$$n$$$ 轮。
您已跟踪洗牌情况并了解庄家手中的牌顺序(从上到下)。你想最大化你的分数,所以你可以交换手中的任意两张牌 不超过一次 (避免引起怀疑)。
确定您可以获得的最大点数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^{5}$$$) — 玩家手中的牌数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_{1}, a_{2}, \ldots, a_{n}$$$ ($$$1 \leq a_{i} \leq 2n$$$) - 玩家手中的牌从上到下的值。
每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_{1}, b_{2}, \ldots, b_{n}$$$ ($$$1 \leq b_{i} \leq 2n$$$) - 庄家手中的牌从上到下的值。
保证所有卡牌的值都是不同的。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 您可以获得的最大分数。
示例
输入复制
3713 7 4 9 12 10 26 1 14 3 8 5 1131 6 52 3 458 6 3 10 17 9 5 2 4
输出复制
6 2 3
注意
在第一个测试用例中,卡片可以保持不变。游戏玩法将组织如下:
- 比较值为 $$$13$$$ 和 $$$6$$$ 的卡片。玩家获胜并获得一分。
- 比较值为 $$$7$$$ 和 $$$6$$$ 的卡片。玩家获胜并获得一分。
- 比较值为 $$$4$$$ 和 $$$6$$$ 的卡片。庄家赢了。
- 比较值为 $$$4$$$ 和 $$$1$$$ 的卡片。玩家获胜并获得一分。
- 比较值为 $$$9$$$ 和 $$$1$$$ 的卡片。玩家获胜并获得一分。
- 比较值为 $$$12$$$ 和 $$$1$$$ 的卡片。玩家获胜并获得一分。
- 比较值为 $$$10$$$ 和 $$$1$$$ 的卡片。玩家获胜并获得一分。
在第二个测试用例中,价值 $$$1$$$ 和 $$$5$$$ 的牌可以交换,那么玩家的手牌看起来如下 $$$[5, 6, 1]$$$。游戏玩法将组织如下:
- 比较值为 $$$5$$$ 和 $$$2$$$ 的卡片。玩家获胜并获得一分。
- 比较值为 $$$6$$$ 和 $$$2$$$ 的卡片。玩家获胜并获得一分。
- 比较值为 $$$1$$$ 和 $$$2$$$ 的卡片。庄家赢了。
在第三个测试用例中,价值$$$3$$$和$$$10$$$的牌可以交换,那么玩家的手牌看起来如下$$$[8,6,10,3,1]$$$。游戏玩法将组织如下:
- 比较值为 $$$8$$$ 和 $$$7$$$ 的卡片。玩家获胜并获得一分。
- 比较值为 $$$6$$$ 和 $$$7$$$ 的卡片。庄家赢了。
- 比较值为 $$$6$$$ 和 $$$9$$$ 的卡片。庄家赢了。
- 比较值为 $$$6$$$ 和 $$$5$$$ 的卡片。玩家获胜并获得一分。
- 比较值为 $$$10$$$ 和 $$$5$$$ 的卡片。玩家获胜并获得一分。