题目内容

从第 1 天起，机器人小队需要统计未来 $n$ 天内的设备维护重叠情况。三台设备分别记为 A、B、C。设备 A 的维护需求出现在第 $x$、$2x$、$3x$、$\ldots$ 天；设备 B 的维护需求出现在第 $y$、$2y$、$3y$、$\ldots$ 天；设备 C 的维护需求出现在第 $z$、$2z$、$3z$、$\ldots$ 天。若某一天至少有两台设备需要维护，则称这一天为“忙碌日”。请计算从第 1 天到第 $n$ 天中忙碌日的总数。

约束：测试数据组数 $T$ 满足 $1 \le T \le 10^5$；总天数 $n$ 满足 $1 \le n \le 10^9$；周期 $x,y,z$ 均满足 $1 \le x,y,z \le 10^4$。

输入描述

第一行输入一个整数 $T$，表示测试数据组数，满足 $1 \le T \le 10^5$。接下来 $T$ 行，每行输入四个整数 $n$、$x$、$y$、$z$，分别表示总天数、设备 A 的维护周期、设备 B 的维护周期、设备 C 的维护周期；保证 $1 \le n \le 10^9$，$1 \le x,y,z \le 10^4$。

输出描述