1358: 数论三角洲（hard version）

这天，三个哈夫克指挥官Libra_Minister , feiwenqiang , xxsars 正齐聚一堂 vp 沈阳区域赛， Libra_Minister 被一个形如 $(m_i + 1) * (n_j + 1)$ 的数论构造从头卡到尾。但聪明的指挥官 Libra_Minister 在补题的时候很快想到了数论中的一个关于剩余系的定理，于是便理解了这个构造，并且想到了一个没那么难但更有意思的数论题目给 NWU-ACM 的新生来挑战一下。题意如下：

给定一个 $n \cdot m$ 的网格区域， $gcd(n , m) = 1$ ，威龙准备在这个区域内藏一下他从邪恶 xjj 的手下抢到的物资，（这很合理，因为 xjj 富得流油，一次性带不走很正常）。整个网格区域中的 $n\cdot m$ 个格子被编号为 $1, 2 , \dots , nm$ ，他只会在 $v$ 满足 $gcd(v , nm) = 1$ 编号 $v$ 的格子中藏物资，威龙想知道有多少个格子是适合藏物资的？

由于区域挺大，适合藏物资的点可能也很多，威龙先生的脑子要过载了，于是威龙从正义的哈夫克阵营指挥官 Libra_Minister 手中申请了脑机接口，但笨蛋威龙是个武将，但他想知道怎么写计算一共有多少个适合藏物资的算法，还请你来帮助他！

第一行输入一个正整数 $t$ ，代表 $t$ 次询问。

每个询问仅有一行输入，包含一个整数 $n(1\leq n \leq 2\times 10^5)$ ，和一个整数 $m(1\leq m \leq 2\times 10^5)$ ，表示网格区域的大小。

输入保证 $\sum n\le 4 \times 10^5$ ，$\sum m \le 4 \times 10^5$ 。

2
3 7
8 9

12
24