You have given an integer array/list ‘arr’ of size ‘N’. You have to split the array into the maximum number of subarrays such that the first and last occurrence of every distinct element lies in a single subarray.

You are required to return the number of maximum subarrays in which the array can be split.

An array ‘C’ is a subarray of array ‘D’ if ‘C’ can be obtained from ‘D’ by deletion of several elements from the beginning and several elements from the end.

For Example:

Let an array ‘arr’ = [2,2,1,1].

In this example, the array can be split like this [2,2], [1,1] in this 
case the first and last occurrence of 2 lies in a first subarray and 
similarly first and the last occurrence of 1 lies in a second 
subarray. 

Input Format:

The first line contains a single integer ‘T’ denoting the number of 
test cases to be run. Then the test cases follow.

The first line of each test case contains a single integer N 
denoting the size of an array. 

The second line of each test contains ‘N’ space-separated i 
integers denoting the elements of the array ‘arr’. 

Output Format:

For each test case, print an integer ‘X’ denoting the maximum number of subarrays in which the array ‘arr’ can be split.

Output for each test case will be printed in a separate line. 

Note:

You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.

Constraints:

1 <= T <= 100
1 <= N <= 10^3
1 <= arr[i] <= 10^5

Time Limit: 1 sec.