Bạn được cho một dãy số có ~n~ phần tử. Mỗi giá trị xuất hiện tối đa ~2~ lần.

Bạn muốn xóa tất cả phần tử trong dãy số này, và bạn được thực hiện hai thao tác sau:

• Xóa hai phần tử kề nhau nếu hai phần tử đó bằng nhau. Sau khi xóa, dãy được dồn lại.
• Đổi chỗ hai phần tử kề nhau.

Hãy in ra số thao tác tối thiểu cần để xóa tất cả các phần tử của dãy số này.

Input

Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 10^5~) - số lượng bộ test.

Dòng đầu tiên của mỗi test gồm một số nguyên dương ~n~ (~1 \le n \le 363636~) - số phần tử của dãy.

Dòng thứ hai của mỗi test gồm ~n~ số nguyên dương ~a_i~ (~1 \le a_i \le 10^9~) mô tả các phần tử của dãy.

Dữ liệu đảm bảo tổng của ~n~ qua mọi test không vượt quá ~676767~.

Output

Với mỗi test, in ra số thao tác tối thiểu cần thiết. Nếu không thể xóa hết dãy, in ra ~-1~.

Sample Input

2
6
1 1 2 2 3 3
6
1 9 9 8 1 8

Sample Output

3
4