Cho dãy ~z~ gồm ~n~ phần tử, được đánh số từ ~1~ đến ~n~. Hãy đếm xem có bao nhiêu bộ bốn số ~(a, b, c, d)~ thỏa mãn ~1 \le a \le b < c \le d \le n~ và không có số nào xuất hiện trong cả hai đoạn ~(z_a, z_{a+1}, \ldots, z_b)~ và ~(z_c, z_{c+1}, \ldots, z_d)~.

Input

Dòng đầu tiên chứa số nguyên ~t~ là số lượng bộ dữ liệu (~1 \le t \le 50~). Mỗi bộ dữ liệu được miêu tả như sau:

• Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 1000~).
• Dòng tiếp theo chứa ~n~ số nguyên ~z_1, z_2, \ldots, z_n~ (~1 \le z_i \le 10^9~).

Output

Với mỗi bộ dữ liệu, in ra một dòng duy nhất chứa số lượng bộ bốn số ~(a, b, c, d)~ thỏa mãn điều kiện đề bài.

Scoring

• Subtask 1 (20% số điểm): ~t = 1, 1 \le n \le 20~.
• Subtask 2 (20% số điểm): ~t \le 5, 1 \le n \le 300~.
• Subtask 3 (30% số điểm): ~t \le 5~.
• Subtask 4 (30% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input

2
3
1 2 5
4
2 3 2 3

Output

5
4

Giải thích

• Với bộ dữ liệu đầu tiên, tất cả các bộ số đều thỏa mãn.
• Với bộ dữ liệu thứ hai, các bộ số thỏa mãn là ~(1,1,2,2), (1,1,4,4), (2,2,3,3), (3,3,4,4)~.