401843: GYM100541 B Sum

Write a program to compute the following sum S given a positive integer n:

, where is the largest integer not greater than x.

The input file consists of several datasets. The first line of the input file contains the number of datasets which is a positive integer and is not greater than 30. The following lines describe the datasets.

Each dataset contains a positive integer n (n ≤ 10¹²) written on a separate line.

For each dataset, write in one line the remainder of the computed sum S divided by 10⁶.

2
1
5

1
10