We always have a friend who loves math and numbers. I have one such guy in my class too who has recently sparked an interest in sequences. He came across a sequence called Sylvester's sequence.

In number theory, Sylvester's sequence is an integer sequence in which the first element of the sequence is 2 and for all others, each member of the sequence is the product of the previous members, plus one.

He now wants to know how these numbers would look like. He started calculating it manually and found that the numbers become huge pretty fast and it was getting difficult for him. As he isn't very good at programming, he wants a program that would give out the sequence.

Given a number N, print the first N members of the sequence.

Since the numbers can be large, output every number in the sequence modulo $10^{9} + 7$.

Input

First line of the input contains a single integer T denoting the number of the test cases. Each of the next T lines follow, with each line containing a single integer N.

Output

For each and every test-case, print the required sequence of integers separated by a single space.

Constraints

$1 ≤ T, N ≤ 10^{5}$

Note

Sum of N over all test cases $\le 2 \times 10^6$