描述

求\(\sum_{i=0}^N \sum_{j=0}^N [3^{ij}\ast (i+j)]\)

输入

第一行一个正整数T
接下来T行
每行一个自然数N

输出

输出T行
每行一个整数
为表达式的值
模998244353

样例

输入

2
1
2

输出

8
390

范围

50% T<=4 N<=3000
100% T<=6 N<=\(10^6\)

限制

1s
64M