该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

鬧吧

我總算找到適者生存的途徑

總有人說的好聽做起來像個逃兵

過河拆橋真的好嗎

但凡是活著就得習慣

這附帶懸念的案情

我大腦都是各種嘴臉在搶鏡

问题描述

给定一个巨大的整数稳定常数 $S$。为了构建稳定的通信谐振器，需要在所有分母 $q$ 满足 $1\le q\le N$ 的有理数 $\frac{p}{q}$ 中，找出使

最小的那一个。输出该最优分数的分子 $p$ 与分母 $q$。要求输出的 $\frac{p}{q}$ 为最简分数。

输入格式

第一行一个整数 $T$（表示测试组数）。 接下来 $T$ 行，每行包含两个整数 $S,N$。

输出格式

对每组数据输出一行，两个用空格分隔的整数 $p,q$，表示找到的最优分数 $\frac{p}{q}$。要求 $\frac{p}{q}$ 为最简分数。

样例

样例输入

3
13 20
112 100
987654321098765432 1000000000

样例输出

18 5
127 12
856475201330956708 861811547

数据范围与约定

• $1\le T\le 10^4$
• $1\le S\le 10^{18}$
• $1\le N\le 10^{9}$