题目描述

背景： 在楼房不断增高的当下，楼房的层数居然达到了2e9层。与人民收入提高相反的是，房价却低到了惊人的100元/平。面对如此低廉的房价，许多夫妇蜂拥而至，打算抢购一套房子。

但是，每对夫妇都有各自想住的楼层，但他们在买房的时候犯了难。对此，没考上大学的知名公众人物——小明，提出：那就买第k层吧（k为夫妇二人各自想住楼层的最大公约数）。

有n对夫妇，他们想住的楼层分别为a和b。

输入格式

第一行输入n，1≤n≤1e5。

接下来n行，输入a和b，1≤a,b≤2e9。

输出格式

输出一个数

样例

2 
3 6 
4 6

3 
2

提示

by 陈代睿