Giả sử chúng ta có mảng \([b_1,b_2,...,b_n]\), và và số cặp nghịch thế của mảng \(b\) chính là số cặp \((i,j)\) thoả mãn: \(1\le i<j\le n\) và \(b_i>b_j\).
Chúng ta gọi mảng \(b\) là "dãy nghịch thế lẻ" nếu số lượng cặp nghịch thế trong mảng \(b\) là số lẻ.

Ví dụ: Mảng \([4,2,7]\) được gọi là: "dãy nghịch thế lẻ" vì số lượng cặp nghịch thế trong mảng này là: \(1\)

Bây giờ, An giao cho bạn một bài toán như sau:

Cho một mảng gồm \(n\) phần tử \([p_1,p_2,...,p_n]\) là hoán vị của \(n\) số nguyên dương đầu tiên (từ \(1\) đến \(n\)). Bây giờ nhiệm vụ của bạn là đặt các vách ngăn giữa các phần tử sao cho số lượng "dãy nghịch thể lẻ" là lớn nhất có thể và in kết quả này ra màn hình

Ví dụ 1: Ta có một hoán vị của \(4\) số nguyên dương đầu tiên: \(4,3,2,1\). Thì chúng ta có thể chia mảng này thành như sau: \(|4,3|,|2,1|\). Khi đó chúng ta thu được số lượng "dãy nghịch thế lẻ" lớn nhất là \(2\) vì \(|4,3|\) và \(|2,1|\) đều là "dãy nghịch thế lẻ"
Ví dụ 2: Ta có một hoán vị của \(3\) số nguyên dương đầu tiên: \(1,2,3\). Thì kết quả là 0. Vì dù chia cách nào đi nữa, thì số lượng "dãy nghịch thế lẻ" là \(0\)

Input

• Dòng đầu tiên chứa số nguyên dương \(t(1\le t\le 100)\) - Thể hiện số testcase
• \(t\) block tiếp theo, mỗi block có dạng như sau:
• ++ Dòng đầu tiên chứa số nguyên dương \(n(1\le n\le 10^4)\) - Thể hiện số lượng phần tử trong mảng
• ++ Dòng tiếp theo gồm \(n\) phần tử \(p_1,p_2,...,p_n\) chính là hoán vị của \(n\) số nguyên dương đầu tiên.

Output

• Ứng với mỗi testcase, hãy in kết quả ra màn hình.

Example

2
2
1 2 3
4
4 3 2 1

0
2