小D的Lemon
题号：NC22592
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

あの日の悲しみさえ
那一天的悲伤也好
あの日の苦しみさえ 
那一天的痛苦也好 
そのすべてを愛してた あなたとともに 
我深爱着和你在一起的点点滴滴 
胸に残り離れない 
残留在心中久久不离 
苦いレモンの匂い 
苦柠檬的香气 
雨が降り止むまでは帰れない 
雨停为止都无法回去 
切り分けた果実の片方の様に 
如同切开的果实的一面那样 
今でもあなたはわたしの光 
至今为止你依然是我的光
米津玄师—《Lemon》
题目描述
旧日的美好已如昙花般绽放之后消失的无影无踪，只剩下些许的回忆和无穷的悔恨。如梦般的时光已经逝去，但值得庆幸的是，仍有电脑、鼠标、键盘和那一串串的公式无言却忠诚地记录着过去。
小D在时光的缝隙中找到了一个公式


若把一个正整数  分解为若干质数的乘积，即，定义

公式的结果，是一段小D重要的回忆，因此小D一直在不停寻找着答案。

人脑可真是个不可靠的磁盘呢——无论是记录还是删除。

雨后的空气格外清新，夹杂着柠檬的香气，青涩而又甘甜。小D探索着公式的奥妙，在数学的海洋里找寻着往昔的光芒。

输入描述:

第一行为一个整数 T ，表示数据的组数
接下来 T 行，每行两个整数 n, m

输出描述:

一共T行，第 i 行输出第 i 组数据的答案，答案对  取模
示例1

输入

复制 
1
4 5

输出

复制 
2

说明

g(1)=g(2)=g(3)=g(5)=1,g(4)=2
当i=4,j=4时，g(gcd(i,j))=2，其他g(gcd(i,j))=1

备注: