该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

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

—— 杨万里 《舟过安仁》

题目描述

求从公元后 $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$。