感觉这场挺难的，vp 连 B 都没搞出来

A. Reorder the Array

排序，双指针贪心一下就好了。

B. Pave the Parallelepiped

题意可以转化为从 A,B,C 的因子中各选一个数组成的本质不同的无序三元组有多少个。

我刚开始想简单了，以为把 A,B,C 排个序然后再枚举前两个就可以了（毕竟 B 题）。实际上这样做明显是错的，因为较大的数不一定包含较小的数的所有因子。那么我们就需要讨论了。

手玩一下可以知道，10^5 以内的数最多有约 100 个因数，所以枚举是不行的。我们考虑把这些因数分类（以 A=9,B=6,C=8 为例）：

可以看出上图的 7 个区域中，两个不同区域的元素是无关的，所以我们只关心每个区域中的元素个数 f(i)，i 为上图所示的区域编号。这可以先线性筛出约数个数再容斥求出。考虑在 A,B,C 三个圆中分别选出一个区域，这样就可以覆盖所有本质不同的状态了。每种选择要讨论一下三种情况：

• 选出的三个区域都相同（即区域7）。此时贡献为 \frac{f(7)[f(7)+1][f(7)+2]}{6}。
• 选出的三个区域有两个相同（设为区域 x），剩下的一个与前两个不同（设为区域 y）。此时的贡献为 \frac{f(x)[f(x)+1]}{2}\cdot f(y)。
• 选出的三个区域都不同（设分别是 x,y,z）。此时贡献为 f(x)f(y)f(z)。

把表打出来可以发现一共有 51 种选出三个区域的方法，因此复杂度为 O(51t)。下面是代码，上面部分说的不够清楚的地方加了注释：

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=110000;
const int C[51][3]={{1, 2, 4}, {1, 2, 5}, {1, 2, 6},
                    {1, 2, 7}, {1, 3, 4}, {1, 3, 5},
                    {1, 3, 6}, {1, 3, 7}, {1, 4, 6},
                    {1, 4, 7}, {1, 5, 6}, {1, 5, 7},
                    {1, 6, 6}, {1, 6, 7}, {1, 7, 7},
                    {2, 3, 4}, {2, 3, 5}, {2, 3, 6},
                    {2, 3, 7}, {2, 4, 5}, {2, 4, 7},
                    {2, 5, 5}, {2, 5, 6}, {2, 5, 7},
                    {2, 6, 7}, {2, 7, 7}, {3, 3, 4},
                    {3, 3, 5}, {3, 3, 6}, {3, 3, 7},
                    {3, 4, 5}, {3, 4, 6}, {3, 4, 7},
                    {3, 5, 5}, {3, 5, 6}, {3, 5, 7},
                    {3, 6, 6}, {3, 6, 7}, {3, 7, 7},
                    {4, 5, 6}, {4, 5, 7}, {4, 6, 7},
                    {4, 7, 7}, {5, 5, 6}, {5, 5, 7},
                    {5, 6, 6}, {5, 6, 7}, {5, 7, 7},
                    {6, 6, 7}, {6, 7, 7}, {7, 7, 7}};
// 以上是 51 种选三个区域的方法

bool mark[MAXN];
int pri[MAXN], d[MAXN], num[MAXN];
void sieve(int lim)
{
    int cnt=0; d[1]=1;
    for (int i=2; i<=lim; i++)
    {
        if (!mark[i])
            pri[cnt++]=i, d[i]=2, num[i]=1;
        for (int j=0; j<cnt&&i*pri[j]<=lim; j++)
        {
            mark[i*pri[j]]=1;
            if (i%pri[j]==0)
            {
                num[i*pri[j]]=num[i]+1;
                d[i*pri[j]]=d[i]/(num[i]+1)*(num[i*pri[j]]+1);
                break;
            }
            d[i*pri[j]]=d[i]*d[pri[j]];
            num[i*pri[j]]=1;
        }
    }
}

int f[10];

int main()
{
//  freopen("B.in", "r", stdin);
//  freopen("B.out", "w", stdout);
    int t;
    scanf("%d", &t);
    sieve(1E5); // 线性筛约数个数
    while (t--)
    {
        int a[3];
        scanf("%d%d%d", &a[0], &a[1], &a[2]);

        for (int s=1; s<=7; s++)
        {
            int g=0;
            for (int i=0; i<3; i++)
                if (s&1<<i) g=__gcd(g, a[i]);
            f[s]=d[g];
            // 注意为了方便，图中的区域编号与二进制码一一对应
            // 两个数的因数的交就是它们 gcd 的因数
        }

        f[3]-=f[7], f[5]-=f[7], f[6]-=f[7];
        f[1]-=f[3]+f[5]+f[7];
        f[2]-=f[3]+f[6]+f[7];
        f[4]-=f[5]+f[6]+f[7];
        // 容斥，把重复算的东西去掉

        int ans=0;
        for (int i=0; i<51; i++)
        {
            int x=C[i][0], y=C[i][1], z=C[i][2];
            if (x==y&&x==z) ans+=f[x]*(f[x]+1)*(f[x]+2)/6;
            else if (x==y) ans+=f[x]*(f[x]+1)/2*f[z];
            else if (x==z) ans+=f[x]*(f[x]+1)/2*f[y];
            else if (y==z) ans+=f[y]*(f[y]+1)/2*f[x];
            else ans+=f[x]*f[y]*f[z];
            // 分别讨论了三种情况，其中第二种还要考虑是哪两个区域相同
        }
        printf("%d\n", ans);
    }
    return 0;
}