Adrian organizes and hosts a birdwatching group for his local community. There is very little bird activity in his area during the winter months, but beginning on the 2nd day of Spring the birds begin to migrate back. Adrian's area happens to be located along a migration route, and so a great variety of bird species will migrate through his area, making the territory renowned for birdwatching.
Over the previous years, Adrian has noticed a pattern
in the migration patterns of the birds. The 1st species of birds will always be
first seen on the 2nd day of Spring and then only seen again every 2 days after that, while the 2nd species of birds
will be first seen on the 3rd day of Spring and then only seen again every 3 days after that. In general, bird species
n will be first seen on day n+1 and only seen again every n+1 days after that. For example, the 6th bird
species will first be seen on day 7, then again on days 14, 21, 28, and so forth, but won't be seen on any
other days.
One day before Spring begins, Adrian recieves a request from a person wishing to sign up for some birdwatching trips. However, they have odd specifics in their request:
2 days for birdwatching. The days do not need to be consecutive.1st day of birdwatching during their 2nd day of birdwatching.1 (on which there will be zero birds).Any two days which satisfy the above conditions are known as a valid pair. The person wants to know how many valid pairs exist from now until the end of the birdwatching season.
For example, let's call the first bird species to arrive A, the next B, and so on. Then assuming that the birdwatching season lasts for only 6 days, the following birds would appear on the following days:
Species | Day #
| 1 | 2 | 3 | 4 | 5 | 6
---------|---|---|---|---|---|---
A | | X | | X | | X
B | | | X | | | X
C | | | | X | |
D | | | | | X |
E | | | | | | X
So the pairs (2, 3), (2, 5), (3, 4), (3, 5), (4, 5), or (5, 6) all form valid pairs.
However the pair (1, 6) is not valid because no birds are seen on day 1.
The pair (4, 6) is also not valid, because bird A could be seen on both days.
You will be given n, the quantity of days within the birdwatching season, where n=1 corresponds to the first day
of Spring. You must then calculate how many pairs of days exist during that time period which share no birds in common yet
at least one bird can be seen.
Input Data
The first line will be Q, the quantity of testcases.
Q lines will then follow, each with a single integer n corresponding to the quantity of days within the birdwatching season.
Answer
Should consist of Q space-separated values, corresponding to the total amount of valid pairs in each testcase.
Example
input data:
9
6
12
21
123
321
1234
4321
1235
54321
answer:
6 34 119 4513 31123 461990 5672897 46314053 896887809