Polycarp was presented with some sequence of integers a of length n (1≤ai≤n). A sequence can make Polycarp happy only if it consists of different numbers (i.e. distinct numbers).

In order to make his sequence like this, Polycarp is going to make some (possibly zero) number of moves.

In one move, he can:

remove the first (leftmost) element of the sequence.

For example, in one move, the sequence [3,1,4,3] will produce the sequence [1,4,3], which consists of different numbers.

Determine the minimum number of moves he needs to make so that in the remaining sequence all elements are different. In other words, find the length of the smallest prefix of the given sequence a, after removing which all values in the sequence will be unique.

Input

The first line of the input contains a single integer t (1≤t≤104) — the number of test cases.

Each test case consists of two lines.

The first line contains an integer n (1≤n≤2?105) — the length of the given sequence a.

The second line contains n integers a1,a2,…,an (1≤ai≤n) — elements of the given sequence a.

It is guaranteed that the sum of n values over all test cases does not exceed 2?105.

Output

For each test case print your answer on a separate line — the minimum number of elements that must be removed from the beginning of the sequence so that all remaining elements are different.

--------------------------------------------

Polycarp 被呈現(xiàn)出一些長度為 n (1≤ai≤n) 的整數(shù) a 序列。 只有當一個序列由不同的數(shù)字（即不同的數(shù)字）組成時，它才能讓波利卡普高興。

為了使他的序列像這樣，波利卡普將進行一些（可能為零）的移動。

他一舉就能：

刪除序列的第一個（最左邊）元素。

例如，在一次移動中，序列 [3,1,4,3] 將產(chǎn)生序列 [1,4,3]，該序列由不同的數(shù)字組成。

確定他需要進行的最少移動次數(shù)，以便在剩余序列中所有元素都不同。 換句話說，找到給定序列 a 的最小前綴的長度，刪除該前綴后序列中的所有值將是唯一的。

輸入

輸入的第一行包含一個整數(shù) t (1≤t≤104) — 測試用例的數(shù)量。

每個測試用例由兩行組成。

第一行包含一個整數(shù) n (1≤n≤2?105) — 給定序列 a 的長度。

第二行包含 n 個整數(shù) a1,a2,…,an (1≤ai≤n) — 給定序列 a 的元素。

保證所有測試用例的 n 值之和不超過 2?105。

輸出

對于每個測試用例，在單獨的行上打印您的答案 - 必須從序列開頭刪除的元素的最小數(shù)量，以便所有剩余元素都不同。

------------------------

倒敘，利用hashmap即可，下面是代碼：