数论对称差

来源：洛谷 P17161（[入门赛 #50] 数论对称差）

题目描述

扶苏有两个整数 $x, y$。她定义 $x,y$ 的数论对称差是恰好满足如下两个条件之一的所有质数 $p$ 的乘积：

• $p$ 是 $x$ 的质因子，但不是 $y$ 的质因子；
• $p$ 是 $y$ 的质因子，但不是 $x$ 的质因子。

如果这样的 $p$ 不存在，定义 $x$ 和 $y$ 的数论对称差是 $1$。

例如，$8$ 和 $9$ 的数论对称差是 $2 \times 3 = 6$，因为 $2$ 是 $8$ 的质因子，但不是 $9$ 的质因子；$3$ 是 $9$ 的质因子，但不是 $8$ 的质因子。

给定两个正整数，请你帮扶苏求出它们的数论对称差。

输入格式

本题单个测试点里有多组测试数据。第一行是一个整数，表示测试数据的数量 $T$。

对每组数据，输入只有一行两个整数 $x, y$。

输出格式

对每组数据，输出一行一个整数表示答案。

样例 #1

样例输入 #1

1
8 9

样例输出 #1

6

样例解释

符合要求的质数 $p$ 包括 $2$ 和 $3$。

样例 #2

样例输入 #2

1
6 12

样例输出 #2

1

样例解释

$6$ 和 $12$ 的质因子集合都是 $\{2,3\}$，不存在符合要求的质数 $p$，答案为 $1$。

提示

数据规模与约定

• 对 $100\%$ 的数据，$1 \le T \le 10^6$，$2 \le x, y \le 10^7$。

提示

• 请注意大量数据输出对程序效率造成的影响。
• $T$ 的末位数字可以帮助你快速判断输入测试点的特殊约定。
• 线性筛预处理 $10^7$ 内每个数的最小质因子，然后对每个数分解出不同质因子；每个数至多 $8$ 个不同质因子（$2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19 = 9699690 < 10^7$）。
• 答案最大接近 $10^{14}$，需要用 long long。

测试点数据说明