题目描述

刻晴在考试中遇到这道题，$n=a_1^2+a_2^2+a_3^2+...+a_k^2$，已知$n,k$，求$a_1,a_2,a_3,...,a_k$非负整数解的个数。比如$n=4,k=4$时，有$5$个解:$(0,0,0,2),(0,0,2,0),(0,2,0,0),(2,0,0,0),(1,1,1,1)$。

输入格式

两个整数$t,k$

之后输入$t$个整数$n$。

输出格式

对于每一对$n,k$，输出一个整数$ans$，表示非负整数解的个数。由于答案过大，请输出$ans \ \%\ 998244353$。

样例

样例输入

5 4
0
1
2
3
4

样例输出

1
4
6
4
5

数据范围与提示

$1\le t,k\le 10^5$

$0\le n \le 10^5$