题目背景

出题人 @GeorgeDeng。

请注意这道题不同寻常的空间限制。

这道题轻微卡常（好像不是轻微）。

如果认为自己时间复杂度正确，请加上快读：

__always_inline long long read(){
    long long x = 0,f = 1;
    char ch = getchar();
    while(ch<'0'&&ch>'9'){
        if(ch=='-') f = 0-f;
        ch = getchar();
    }
    while(ch>='0'&&ch<='9'){
        x = x*10+(ch-'0');
        ch = getchar();
    }
    return x*f;
}

函数的返回值为第一个读到的整数。

如果还是过不了，请在除了主函数外的所有函数前面加上 __always_inline 修饰。

请务必保证你的时间复杂度为 \(O(n \log n)\)。

题目描述

定义两个整数 \(a\) 和 \(b\) 为逆序对个数如下：

• 如果 \(a\) 的一个质因数比 \(b\) 中一个质因数大的对数，则称 \(a\) 和 \(b\) 组成逆序对个数，记为 \(n(a,b)\)。
• 例如：\(8\) 和 \(14\)。因为 \(8=2^3,14=2\times7\)，\(8\) 的质因数只有 \(2\)，\(14\) 的质因数有 \(2\) 和 \(14\)。\(8\) 的质因数中没有比 \(14\) 的质因数大的，所以我们称 \(8\) 和 \(14\) 形成了 \(0\) 个逆序对，\(n(8,14)=0\)。
• 反过来，\(14\) 的质因数有 \(1\) 个比 \(8\) 大的（\(7\) 和 \(2\)），所以我们称 \(14\) 和 \(8\) 形成了 \(1\) 个逆序对，\(n(14,8)=1\)。

现在有一个长度为 \(n\) 的数组 \(A\)，请求出 \(A\) 里的逆序对个数，即 \(\sum n(A_i,A_j)\) \((i<j)\)。

输入格式

本题包含多组测试数据。

输入文件的第一行一个正整数 \(T\)，表示测试数据的组数。

对于每组测试数据，第一行是一个整数 \(n\)，表示数组长度，第二行 \(n\) 歌整数 \(A_i\)，表示数组。

输出格式

对于每一组测试数据，输出它的逆序对个数 \(\sum n(A_i,A_j)\) \((i<j)\)。

输入输出样例 #1

输入 #1

2
2
8 14
2
14 8

输出 #1

0
1

说明/提示

数据范围与约定

对于 \(20\%\) 的数据，\(1\le n \le 100\)。

对于 \(50\%\) 的数据，\(1\le n \le 10^4\)。

对于 \(100\%\) 的数据，\(1\le T \le 3,1\le n \le 3\times 10^5,1\le A_i \le 3\times 10^5\)，保证运算中所有数均在 \(64\) 位有符号整数的表示范围内。