Processing math: 100%

E. 2..3...4.... Wonderful! Wonderful!
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Stack has an array a of length n such that ai=i for all i (1in). He will select a positive integer k (1kn12) and do the following operation on a any number (possibly 0) of times.

  • Select a subsequence s of length 2k+1 from a. Now, he will delete the first k elements of s from a. To keep things perfectly balanced (as all things should be), he will also delete the last k elements of s from a.

Stack wonders how many arrays a can he end up with for each k (1kn12). As Stack is weak at counting problems, he needs your help.

Since the number of arrays might be too large, please print it modulo 998244353.

A sequence x is a subsequence of a sequence y if x can be obtained from y by deleting several (possibly, zero or all) elements. For example, [1,3], [1,2,3] and [2,3] are subsequences of [1,2,3]. On the other hand, [3,1] and [2,1,3] are not subsequences of [1,2,3].

Input

Each test contains multiple test cases. The first line contains a single integer t (1t2103) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer n (3n106) — the length of the array a.

It is guaranteed that the sum of n over all test cases does not exceed 106.

Output

For each test, on a new line, print n12 space-separated integers — the i-th integer representing the number of arrays modulo 998244353 that Stack can get if he selects k=i.

Example
Input
4
3
4
5
10
Output
2 
4 
10 2 
487 162 85 10 
Note

In the first test case, two a are possible for k=1:

  • [1,2,3];
  • [2].

In the second test case, four a are possible for k=1:

  • [1,2,3,4];
  • [1,3];
  • [2,3];
  • [2,4].

In the third test case, two a are possible for k=2:

  • [1,2,3,4,5];
  • [3].