Kinich ngủ dậy và nhận được một hộp quà bất ngờ ở trên điện thoại của mình. Anh ấy quyết định mở nó ra và phát hiện nó là một trò chơi. Người chơi được cho một mảng ~a~ có ~N~ phần từ và bắt đầu với ~0~ điểm.

Một vòng chơi sẽ được thực hiện như sau:

• Chọn 2 phần từ ~a_i~ và ~a_j~ trong đó ~i~ và ~j~ chưa được chọn lần nào trước đó, và ~a_i = a_j~. Hành động này cho người chơi ~1~ điểm

Là một gamer, Kinich muốn phải tối đa điểm cho trò chơi này nên đã chơi nó rất nhiều lần. Cho ~T~ lần chơi của Kinich, hãy in ra số điểm lớn nhất mà Kinich có thể đạt được sau mỗi lần chơi.

Input

Dòng đầu tiên chứa số nguyên ~T~: số test case / số lần Kinich đã chơi

Dòng đầu tiên của mỗi test case chứa số nguyên ~N~: kích thước của mảng ~a~ trong trò chơi

~N~ số tiếp theo: các phần từ của mảng ~a~

Output

In ra ~T~ dòng, dòng thứ ~i~ là số điểm tối đa Kinich có thể đạt được trong lần chơi thứ ~i~

Giới hạn

~1 <= T <= 1000~

~1 <= N <= 1000~

Test mẫu

Input

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

Output

0
1
0
1
3