Cho dãy số ~a_1,a_2,…,a_n~. Hỏi tồn tại bao nhiêu cặp ~l~, ~r~ thỏa mãn sao cho mọi phần tử trong đoạn [~l,r~] (~l ≤ r~) đều đôi một khác nhau.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương ~t~ – số test case (~1≤ t ≤ 100~).
• Dòng đầu tiên của mỗi test case chứa số nguyên dương ~n~ (~1≤ n ≤ 200000~).
• Dòng tiếp theo chứa ~n~ số nguyên lần lượt là ~a_1,a_2,…,a_n~ (~1≤ a_i ≤ 10^9~).

Dữ liệu ra:

• Gồm ~t~ dòng, mỗi dòng là một số nguyên dương ~x~ duy nhất với ~x~ là số cặp ~l – r~ thỏa mãn tất cả các phần tử trong đoạn [~l,r~] đều đôi một khác nhau.

Ví dụ:

Input

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

Output

9
7