You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

一叶渔船两小童，收篙停棹坐船中。怪生无雨都张伞，不是遮头是使风。

—— 杨万里 《舟过安仁》

题目描述

求从公元后 $1$ 年至公元后 $n$ 年有多少年为快乐年？

快乐年的定义为：能被 $a$ 整除且不能被 $b$ 整除，或者是能被 $c$ 整除的年份，即将闰年定义中的 $4,100,400$ 依次替换为 $a,b,c$。

输入格式

本题有多组数据。

第一行一个整数 $T$，表示数据组数。

对于每组数据：

一行四个整数 $n,a,b,c$，表示公元后 $n$ 年，快乐年定义中的 $a,b,c$。

输出格式

输出一个数，表示答案。

5
2024 5 4 7
1024 5 10 15
114514 5 3 9
998244 3 5 3
353998 7 9 6

549
136
27991
332748
98332

提示

对于 $100\%$ 的数据，$1\le T\le 10^5$，$1\le n\le 10^{18}$，$1\le a,b,c\le 10^9$。