H. 追忆
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
若花胜去年红，坞中莲蕊竟已开已落，醉倒芳丛，一眼岁月都无穷。
— 东风志

年少时的时光，总是与许多独特的景象相伴：或许是那一缕东风，或许是那一片柳絮，又或许是那一抹剑光、一盏浊酒、一地月光。这些景象早已远去，化作一行行诗句。

你翻阅这卷诗，仿佛又重新走过了那些岁月。诗卷共有 n 行，第 i 行诗描述了第 i 个景象 ai，相同的景象可能出现在不同的行中。你打算从中选取连续的一段区间 [l, r]，作为你最深刻的"忆境"。你认为，一段忆境的价值，不仅在于其中包含了多少种独特的景象，也在于其之外保留了多少种独特的景象。换言之，忆境的价值等于这段诗中不同景象的种类数加上这段诗外不同景象的种类数。

你想知道，忆境的可能的最大价值是多少？

简要题意

给出一个长度为 n 的序列 a，你需要找到一个区间 [l, r]，使得该区间中不同的数个数加上该区间外不同的数个数之和最大。请给出这个最大值。

Input

本题含有多组测试数据。

第一行输入一个整数 T，表示测试数据组数。

对于每组测试数据：

第一行输入一个整数 n，表示序列 a 的长度。

接下来第二行包含 n 个整数，第 i 个整数表示 ai。

Output

对于每组测试数据：

一行包含一个整数表示答案。

Example
Input
2
4
1 2 2 1
4
1 2 1 2
Output
4
4
Note

对于 100% 的数据，。