#1022. 萨斯噶joker!(hard version)

内存限制:256 MiB 时间限制:1500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: new_user_2

题目描述

ComistryMo暑假打通了P5R之后,意外获得了怪盗团的力量,穿越到了异世界。但是他没有进行二周目,给邪恶的大人们发出预告信,而是沉迷于大富翁

但是他太菜了!以至于芳泽霞学妹必须给ComistryMo放牌! 作为团长,为了捍卫自己的威严,他决定与怪盗团成员玩数学游戏来取代大富翁。

他出的题目是这样的:给定T组数据,每组数据包含两个整数n,m,请求出 gcd(i,j)。

但是ComistryMo不会做这个题目,因此他想请聪明的你们来帮助他,解决此题,维护团长的尊严!

作为热心的怪盗团团长,joker告诉你们gcd(a,b)表示a与b的最大公因数。

输入格式

第一行一个整数T

接下来T行,每行两个整数n,m

输出格式

一共T行,每行一个整数,表示答案

样例

样例输入

3
100 200
1000 2000
1000000 2000000

样例输出

63542
9067212
17457854316166

数据范围与提示

对于所有数据,保证