Chiaki is interested in an infinite sequence , which defined as follows:
where is the smallest positive integer not in the set .
Chiaki would like to know the sum of the first terms of the sequence, i.e. . As this number may be very large, Chiaki is only interested in its remainder modulo .
输入格式
There are multiple test cases. The first line of input contains an integer (), indicating the number of test cases. For each test case:
The first line contains an integer () without leading zeros.
输出格式
For each test case, output an integer denoting the answer.
