[AdditionalFile5593.zip](file://AdditionalFile5593.zip?type=additional_file)

#5593. 「PA 2017 Final」Trenerzy

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

题目译自 PA 2017 Final Trenerzy

字节大学的代表队成功晋级了世界大学生程序设计竞赛总决赛！教练 Marcin 和 Michał 的职责是为即将到来的比赛做好最充分的准备。为此，他们希望在距离比赛开始剩下的 $n$ 天里，每天都为他们的队伍进行一次训练。为了让某一天的训练能够顺利进行，他们必须在早上打印好题目并启动在线竞赛系统，然后在下午与队伍讨论题目的解法。

Marcin 和 Michał 每天都会来大学。Marcin 通常只在早上待在那里，但每隔 $a$ 天，他必须去处理一些公务，因此他会在下午才到大学。Michał 则通常在下午待在大学，但每隔 $b$ 天，他会和女朋友去看电影，因此他会在早上工作。如果在早上或下午，两位教练都不在大学，那么当天的训练就必须取消。

Marcin 可以选择在接下来的 $a$ 天中的某一天第一次去处理公务；同样，Michał 也可以选择在接下来的 $b$ 天中的某一天第一次去看电影。如果 Marcin 和 Michał 能够优化他们的日程安排，那么最多可以进行多少次训练呢？

输入格式

输入的第一行包含一个整数 $t$ $(1 \le t \le 100000)$，表示输入中包含的测试数据组数。

接下来的 $t$ 行，每行描述一组测试数据，包含三个整数 $n, a, b$ $(1 \le n \le 10^{18}, 1 \le a, b \le 10^9)$，分别表示距离比赛剩下的天数、Marcin 去处理公务的频率，以及 Michał 去看电影的频率。

输出格式

对于每组测试数据，在单独的一行中输出一个整数，即在比赛前最多可以进行的训练次数。

样例

输入

2
5 2 3
10 7 2

输出

3
6

以下方案描述了 Marcin 和 Michał 的一种最优日程安排样例。叉号（$\times$）表示教练在该天改变了他的常规日程。

在第一个方案中，训练将在前三天进行。在第二个方案中，训练将在第 $2, 4, 5, 6, 8, 10$ 天进行。