tarjen 有一个长度为 $n$ 的排列 $p$。你最多可以执行一次操作：选择两个整数 $l$ 和 $r$（$1 \le l \le r \le n$）并翻转子数组 $p_l, p_{l+1}, \dots, p_r$。

操作后排列中逆序对的最大数量是多少？

逆序对是指满足 $1 \le i < j \le n$ 且 $p_i > p_j$ 的下标对 $(i, j)$。

输入格式

第一行包含一个整数 $T$（$1 \le T \le 10^5$）—— 测试用例的数量。

每个测试用例：

• 第一行包含一个整数 $n$（$1 \le n \le 8000$）—— 排列的长度。
• 第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$）—— 该排列。

所有测试用例中 $n$ 的总和不超过 8000。

输出格式

对于每个测试用例，输出一个整数 —— 逆序对的最大数量。

样例

输入样例 1

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

输出样例 1

2
10
10

说明

翻转区间 $[1, 3]$ 得到 $[3, 1, 2]$，它有 2 个逆序对：$(1, 2)$ 和 $(1, 3)$。