题目描述

张老师最近在看《最强大脑》节目，然后张老师突然发觉自己原来很强！张老师对一个很大的正整数 $n$，他可以一秒钟找到 $n$ 以内有几个数是 $a$ 或者 $b$ 的倍数。突然发现自己这么强，张老师已经感觉自己已经可以上天了，计算机都没办法跟他肩并肩。所以请同学们帮忙让张老师清醒一点，告诉他计算机也可以轻松做到这件事情。

输入格式

第一行一个整数 $t$（$1 \leq t \leq 10^5$）表示有 $t$ 组数据； 接下来 $t$ 行，每行 3 个整数 $n, a, b$（$1 \leq a, b, n \leq 2 \times 10^9$）。

输出格式

对于每一组数据输出一行，每行一个整数表示 $n$ 以内 $a$ 或者 $b$ 倍数的个数。

样例输入

3
10 2 3
10 3 4
10 4 5

样例输出

7
5
4