Description

$\dfrac{1}{\frac{2\sqrt 2}{99^2}\times \sum\limits_{k=0}^{+\infty}\frac{26390k+1103}{396^{4k}}\times \frac{(4k)!}{k!}}$

Format

Input

一行，一个整数，$t$。

接下来 $t$ 行，每行一个整数 $n$。

Output

$t$ 行，每行一个非负整数。

Samples

5
5
3
4
1
2

9
1
5
1
4

Limitation

对于所有测试数据，满足 $t=1000$，$1\leq n\leq 1000$。