Nikita has a row of white tiles indexed from to . This time, she's painting them green!
Find the number of ways Nikita can paint certain tiles in green so that the indices of the green tiles form an Arithmetic Progression. As this value can be quite large, your answer must be modulo .
Note: Nikita must paint at least tile.
Input Format
The first line contains a single integer, , denoting the number of test cases.
Each test case consists of a single line containing an integer, , denoting the length of row of tiles.
Constraints
Scoring
- for of test data.
- for of test data.
- for of test data.
Output Format
On a new line for each test case, print the number of ways Nikita can paint her white tiles green so that the indices of the green tiles form an Arithmetic Progression. Because this number can be quite large, your answer must be modulo .
Sample Input
3
3
4
5
Sample Output
7
13
22
Explanation
Test Case 0:
There are valid ways to paint the tiles:
Thus, we print the result of on a new line, which is .
Test Case 1:
There are valid ways to paint the tiles:
Thus, we print the result of on a new line, which is .