题目描述
小J是一个严谨的人,他只能接受有限小数,而总有些数令他不爽,比如0.33...。一天,他发现0.33…在3进制下可以写成0.1,在30进制下可以写成0.A等,于是他坚信所有有理数都可以写成有限小数。然而,不断切换进制是很麻烦的工作,现在小J需要处理若干有理数,你需要告诉他最少需要几进制才能使它们都能写成有限小数。
【数据范围】
100%的数据保证n≤10,000;1≤a,b≤1,000,000,000
【注释】
十六进制使用[0-9,A-F],具体表示方法请参照windows自带计算器
输入格式
第一行一个整数n
接下来n行,每行两个整数a b,表示一个分数a/b
输出格式
一行一个十六进制整数,表示最小进制数
样例输入
样例输出