Bithuania 大学队已经获得了 ACM ICPC 世界总决赛的参赛资格！现在，教练 Martin 和 Michael 希望尽可能好地为队伍进行备战。为了实现这一目标，他们想要为接下来的 $n$ 天制定一个训练计划。若要在某一天进行训练，他们需要在上午打印任务并启动网络竞赛系统，并在下午与参赛选手讨论题目。

Martin 和 Michael 每天都会出现在大学。通常情况下，Martin 每天上午都在，但每隔恰好 $a$ 天，他需要去当地政府办公室处理一些事务，因此在这些天里，他只会在下午出现在大学。同样地，Michael 通常每天下午都在，但每隔 $b$ 天他会陪女朋友去看电影，因此在这些天里，他只会在上午出现在大学。如果某天上午或下午没有教练在大学，则必须取消当天的训练。

Martin 可以选择在接下来的 $a$ 天中的哪一天第一次去办公室。同样地，Michael 也可以选择在接下来的 $b$ 天中的哪一天第一次陪女朋友去看电影。如果 Martin 和 Michael 能够最优地确定他们的日程安排，那么最多可以进行多少天的训练？

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 100\,000$)，表示测试用例的数量。接下来的 $t$ 行，每行描述一个测试用例，包含三个整数 $n, a, b$ ($1 \le n \le 10^{18}, 1 \le a, b \le 10^9$)，含义如上所述。

输出格式

对于每个测试用例，输出一个整数，表示可以进行训练的最大天数。

样例

输入 1

2
5 2 3
10 7 2

输出 1

3
6

说明

在第一个样例中，Martin 和 Michael 都应该在第 2 天第一次偏离他们各自的常规日程安排。这样，前 3 天都可以进行训练。

在第二个样例中，Martin 和 Michael 分别应该在第 5 天和第 1 天第一次偏离他们的常规日程安排。这样，在第 2, 4, 5, 6, 8 和 10 天可以进行训练。