Background

A lone fishing boat with two small children,
They pull in the pole and stop the oars, sitting in the boat.
Strange indeed: though there is no rain, they all open umbrellas,
Not to cover their heads, but to catch the wind.

— Yang Wanli, "Passing Anren by Boat"

Problem Description

How many years from AD $1$ to AD $n$ are happy years?

A happy year is defined as: a year that is divisible by $a$ but not divisible by $b$, or a year that is divisible by $c$. That is, in the leap year rules, replace $4,100,400$ with $a,b,c$ respectively.

Input Format

This problem has multiple test cases.

The first line contains an integer $T$, the number of test cases.

For each test case:

One line contains four integers $n,a,b,c$, representing the year AD $n$, and $a,b,c$ in the definition of a happy year.

Output Format

Output one number, the answer.

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

Hint

For $100\%$ of the data, $1\le T\le 10^5$, $1\le n\le 10^{18}$, $1\le a,b,c\le 10^9$.

Translated by ChatGPT 5