P12226 "WyOJ Round 1" Qi · Breaking the Cocoon, Rising Sun

> 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"

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.

**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 one number, the answer.

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$. | Test Point | Special Property | | :-----------: | :-----------: | | $1\sim 4$ | $1\le T\le 5$, $1\le n\le 10^6$ | | $5\sim 10$ | No special properties. | Translated by ChatGPT 5