题目描述

给定正整数 $n,\ a,\ b$，且满足 $a < b$。

对于满足 $1 \leq L \leq R$ 的整数对 $(L, R)$，如果满足以下条件，则称其为良好组：

• 在 $L$ 到 $R$ 之间的所有整数中，$a$ 的倍数的个数为 $n_a$，$b$ 的倍数的个数为 $n_b$，若 $n_a - n_b = n$，则 $(L, R)$ 为良好组。

可以证明，良好组一定存在。在所有良好组中，输出 $R-L$ 最大的那一个。如果有多个满足条件的组，则输出其中 $L$ 最小的那一个（由于 $1 \leq L$，所以一定存在 $L$ 最小的组，且答案唯一）。

给定 $T$ 组测试数据，请分别输出每组的答案。

输入格式

输入按以下格式从标准输入给出：

$T$
$\text{case}_1$
$\vdots$
$\text{case}_T$

每组测试数据格式如下：

$n\ a\ b$

输出格式

请输出 $T$ 行，第 $i$ 行输出第 $i$ 组测试数据的答案，即所求的 $(L, R)$，格式如下：

$L\ R$

样例 1

输入

1
3 3 5

输出

4 35

样例 2

输入

5
4 3 5
6 2 4
1 1 2
123 456 789
9876 54 321

输出

10 50
3 29
2 4
5473 140447
163 641411

说明/提示

数据范围

• $1 \leq T \leq 2 \times 10^5$
• $1 \leq n \leq 10^6$
• $1 \leq a < b \leq 10^6$

样例解释 1

$(L, R) = (4, 35)$ 时，$n_a = 10,\ n_b = 7$，因此是良好组。其他如 $(1, 26)$、$(10, 41)$ 也是良好组。在这些组中，$(1, 26)$ 的 $R-L$ 不是最大值，所以不是答案；$(10, 41)$ 的 $R-L$ 虽然最大，但 $L$ 不是最小，所以也不是答案。

由 ChatGPT 4.1 翻译