Batch-24 is hosting a "Pre-IUT Meetup" at Smashed Burgers. As part of the registration process, the organizers created registration forms with unique form IDs starting from $$$1$$$ and increasing sequentially.
When registration ended, the organizers found that the number of submissions greatly exceeded the actual number of students in their batch. After the investigation, they discovered that impostors from other batches had also filled out the forms. They examined a few impostor entries and were relieved to find a pattern. An entry is made by an impostor if for the form ID $$$x$$$, $$$x^2 - 1 \text{ is divisible by 24} \quad \text{i.e.,} \quad (x^2 - 1) \equiv 0 \pmod{24}.$$$
Your task is to count the total number of impostors among the first $$$N$$$ form submissions to maintain the Glory of 24!
The first line of the input contains a single integer $$$T$$$ ($$$1 \leq T \leq 10^5$$$) — the number of test cases.
Each test case consists of a single line containing a single integer $$$N$$$ ($$$1 \leq N \leq 10^{18}$$$) — the total number of forms submitted.
For each test case, output a single integer in a line — the number of impostors.
41913456100000000
13448533333333
| Name |
|---|


