B. Sum
time limit per test
2 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

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

, where is the largest integer not greater than x.

Input

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 ≤ 1012) written on a separate line.

Output

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

Examples
Input
2
1
5
Output
1
10