Minimum Contiguous Distinct Subarrays

You are given several test cases. In each test case, you are provided with an integer n and a sequence of n integers. Your task is to partition the given sequence into the minimum number of contiguous subarrays such that each subarray contains only distinct elements.

Formally, for a given sequence a₁, a₂, \dots, a_n, you need to split it into k contiguous parts so that for each part, if it spans indices l to r, then the set \(\{a_l, a_{l+1}, \dots, a_r\}\) has no duplicates. You should choose the partitioning that minimizes k.

The process can be thought of as scanning the sequence from left to right and whenever you encounter an element that you have already seen in the current contiguous subarray, you start a new subarray beginning with that element.

The mathematical formulation is as follows:

[ \text{Let } f(a_1,a_2,\dots,a_n) = \min{ k \mid a_1,a_2,\dots,a_n \text{ can be partitioned into } k \text{ subarrays with all distinct elements} } ]

inputFormat

The input is read from standard input (stdin) and is formatted as follows:

T
n1
a1 a2 ... an1
n2
a1 a2 ... an2
...

Here, T is the number of test cases. For each test case, the first line contains an integer n representing the size of the sequence, and the next line contains n space-separated integers.

outputFormat

For each test case, print the minimum number of contiguous subarrays (each with distinct elements) on a separate line to standard output (stdout).

## sample

3
4
1 2 1 2
6
4 4 4 4 4 4
5
1 2 3 4 5

2
6
1

</p>