题目描述

最大公约数：指能够整除多个整数的最大正整数，而多个整数不能都为零，例如8和12的最大公约数为4。

最小公倍数：两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数，例如12和15的最小公倍数为60。

注意：如果已知两个正整数a,b的最大公约数为g，那么a,b的最小公倍数为c=a×b÷g。

我们称两个数字的最小公倍数的质因数为这两个数的最小公倍质因数，比如：9与21的最小公倍数是63，63有3与7这两个质因数，因此3与7为9与21的最小公倍质因数。

现在小珅同学有n对正整数，他希望你对于每一对数xi,yi，从小到大依次输出它们最小公倍质因数，请你帮它解决。

输入格式

第一行一个正整数n；

接下来n行，每行两个正整数xi,yi

输出格式

对于每一对xi,yi，从小到大依次输出它们的最小公倍质因数，用空格隔开，最后换行，如果一对xi,yi没有最小公倍质因数，输出 "None"。

样例输入

2
2 3
9 21

样例输出

2 3
3 7

输入样例 #2

1
1 1

输出样例 #2

None

输入样例 #3

1
5 69

输出样例 #3

3 5 23

数据范围与提示

数据范围：

对于30% 的数据：1≤xi,yi≤10^2，1≤n≤10^2；

对于60% 的数据：1≤xi,yi≤10^4，1≤n≤10^3；

对于100% 的数据：1≤xi,yi≤10^9，1≤n≤10^3。