Sắp xếp xen kẽ chẵn lẻ

William có một mảng gồm $n$ số nguyên $a_1,a_2,\dots ,a_n$. Trong một bước, anh ấy có thể đổi chỗ hai phần tử liền kề (hai phần tử $a_i$ và $a_j$ được gọi là liền kề nếu $|i-j|=1$).

William muốn bạn tính số bước đổi chỗ ít nhất để mảng không còn hai phần tử liền kề nào có cùng tính chẵn lẻ.

Dữ liệu vào

Dòng đầu chứa số nguyên $t$ là số bộ test ($1\le t\le {10}^4$).

Mỗi bộ test có cấu trúc:

• Dòng đầu chứa số nguyên $n$ là độ dài mảng ($1\le n\le {10}^5$).
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ ($1\le a_i\le {10}^9$).

Tổng các giá trị $n$ trên tất cả các bộ test không vượt quá ${10}^5$.

Dữ liệu ra

Với mỗi bộ test, in ra số phép đổi chỗ tối thiểu cần thiết, hoặc $-1$ nếu không thể đạt được trạng thái mà không có hai số liền kề nào có cùng tính chẵn lẻ.

Ràng buộc

• $1\le t\le {10}^4$
• $1\le n\le {10}^5$
• $1\le a_i\le {10}^9$
• Tổng $n$ không vượt quá ${10}^5$.

Ví dụ