Description

一长方形电路板两长边分别有n个焊点, 分别记作1,2,...,n. 现需要将一边的焊点与另一边的焊点用导线相连, 
共需要n条导线连接n对焊点. 我们用(i,xi)来表示一根导线的连接方式, 即一边的第i点与另一边的第xi相连. 
两条导线(i,xi)和(j,xj)交叉, 当i<j且xi>xj, 或者i>j且xi<xj.

当给定焊点的连接方式时, 请设计一分治算法计算有交叉点的个数.

Input

第一行输入m表示有m组测试. 每组测试首先输入n (n<50000)，接下来输入n个int型整数, 表示xi.

Output

对每组测试数据输出交叉点的个数

Sample Input

2
8 
2 5 1 7 6 3 8 4
8
3 1 6 8 2 5 4 7

Sample Output

10
10