Time Limit: 1000MS Memeory Limit:65536KB

Description

求所有由1-9组成的长度为n的序列逆序对总数。

 

Input

第1行为输入组数

第2—T+1行为长度

答案模上.

 

Output

每组样例输出一行。

 

Sample Input

1

2

 

Sample Output

36

 

Hint

比如 n等于2时:

(2,1),(3,1),(3,2),...(9,8)共36个.