Barisore 喜欢研究树，也喜欢研究数。
我们知道，一个树上节点的父亲是它的祖先中深度最大的。 Barisore 认为，一个正整数的“父亲”，是它所有约数中最大的那个，比如 的父亲是 ， 的父亲是 。
Barisore 痴迷于 LCA（树上最近公共祖先）问题，于是她向你提出了 个问题，每个问题给了你两个正整数 和 ，她想知道它们的“LCA”是多少。
第一行一个正整数 ，表示询问个数。
接下来 行，每行两个正整数 和 ，表示一个询问。
输出 行，对于每个询问输出一个数表示答案。
2 100 50 18 12
50 3
的父亲是 ； 的父亲是 ， 的父亲是 ， 和 的父亲都是 。
设 为所有输入 的最大值。
对于 40% 的数据，;
对于 70% 的数据，;
对于 100% 的数据，。
由于输出输出量过大，请不要使用过慢的输入输出方式（如未关同步的 cin/cout）。