题目背景

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

—— 杨万里 《舟过安仁》

题目描述

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

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

输入格式

本题有多组数据。

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

对于每组数据：

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

输出格式

输出一个数，表示答案。

输入输出样例 #1

输入 #1

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

输出 #1

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$。

\begin{array}{|c|c|} \hline \textbf{测试点} & \textbf{特殊性质} \\ \hline 1\sim 4 & 1\le T\le 5\textbf{，}1\le n\le 10^6 \\ \hline 5\sim 10 & \textbf{无特殊性质} \\ \hline \end{array}