Description

小桂同学刚刚通过寒假算法集训学习到了如何求出$n$的全排列。小桂同学很喜欢连续的递增的数字，现在他想要知道对于$n$的全排列，有多少种排列是至少有$n-1$个连续的递增数字。

注意：

单个数字认为是长度为1的连续递增数字。

0个数字认为是长度为0的连续递增数字。

Input Format

第一行输入一个正整数$t(1≤t≤1000)$，表示有$t$组测试样例。对于每组测试样例，输入一个正整数$n(1≤n≤100000)$。

Output Format

对于每组测试样例，输出一个正整数，表示答案。

1
3

5

Hint

$3$的全排列有以下$6$种：

$(1,2,3)$

$(1,3,2)$

$(2,1,3)$

$(2,3,1)$

$(3,2,1)$

$(3,1,2)$

其中只有$(3,2,1)$不符合要求，所以答案是$5$。

Source

Online Judge http://127.0.0.1