Cho một mảng a gồm n phần tử ~a_1~, ~a_2~, ... ~a_n~.

Gọi độ bất ngờ của x trong mảng a là số lần xuất hiện của x trong mảng a.

Giá trị v được gọi là giá trị tăng động khi và chỉ khi độ bất ngờ của v trong mảng a là lớn nhất. Ví dụ mảng a = [1, 3, 2, 1, 4, 1, 2], thì 1 là tăng động vì có độ bất ngờ là 3 và là độ bất ngờ lớn nhất. Còn mảng [1, 2, 2, 1] có hai phần tử 1 và 2 đều có độ bất ngờ là 2 nên mảng a không có giá trị tăng động.

Bây giờ bạn hãy tìm mảng con có giá trị tăng động sao cho độ dài của mảng con là nhỏ nhất.

Mảng con là dãy các phần tử liên tiếp ~a_l~, ~a_{l+1}~, ... ~a_r~ sao cho (1 ≤ l ≤ r ≤ n)

Input

Dòng đầu tiên là số test case t (2 ≤ t ≤ 5).

Mỗi test case gồm hai dòng:

Dòng thứ nhất chứa một số nguyên n.

Dòng thứ hai là dãy ~a_1, a_2, ... a_n ~

Subtask 1 (35% điểm): ~1 ≤ n ≤ 10^2, 1 ≤ a_i ≤ 10^2~

Subtask 2 (35% điểm): ~1 ≤ n ≤ 10^3, 1 ≤ a_i ≤ 10^3~

Subtask 3 (30% điểm): ~1 ≤ n ≤ 10^5, 1 ≤ a_i ≤ 10^5~

Output

Gồm t dòng, mỗi dòng là câu trả lời của mỗi test case tương ứng - độ dài mảng con nhỏ nhất và có giá trị tăng động.

Examples

Input

3
7
1 3 2 4 5 1 2
3
1 2 3
5
1 2 3 2 1

Output

5
-1
3