大家或许都知道数组的逆序对（inverse number）。

数组 $\{a_1, a_2, \dots, a_n\}$ 的逆序对定义为满足 $a_i > a_j$ 的数对 $(i, j)$ 的数量（其中 $i < j$）。

现在，一个有趣的男孩 Han Min 正在思考数组的一种“新逆序对”。

如果 $i$ 和 $j$ 的奇偶性相同且 $a_i > a_j$，那么他认为 $(i, j)$ 是一个逆序对。如果 $i$ 和 $j$ 的奇偶性不同且 $a_i < a_j$，那么他也认为 $(i, j)$ 是一个逆序对。

换句话说，当 $i$ 和 $j$ 的奇偶性相同时，若 $a_i > a_j$，则索引对 $(i, j)$ 是一个逆序对；否则（即奇偶性不同时），若 $a_i < a_j$，则索引对 $(i, j)$ 也是一个逆序对。

你是 Han Min 的好朋友，现在受雇计算该数组中这种“新逆序对”的数量。你能解决这个问题吗？

输入格式

输入文件的第一行包含一个整数 $T$ ($1 \le T \le 5$)，表示测试用例的数量。

每个测试用例的第一行包含一个整数 $N$ ($1 \le N \le 5000$)，表示数组的长度。

每个测试用例的下一行包含 $N$ 个实数，数与数之间仅用一个空格分隔。

输出格式

输出一个整数，即该数组中“新逆序对”的数量。

样例

输入 1

1
5
1 4 3 2 5

输出 1

5