You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

篮子（basket）

【题目描述】 有一个篮子，里面装了一些球。初始装了颜色为 $0,1,2, \ldots, 500$ 的球各 1 个。给定正整数 $N, K(2 \leq N \leq 200,1 \leq K \leq 200)$ ，你可以任意次（包括 0 次）重复以下操作：

1． 从篮子里选择一个颜色为 $x(2 \leq x \leq N)$ 的球，将其从篮子内拿出； 2． 如果颜色为 $x-2$ 的球不在篮子里，将一颗颜色为 $x-2$ 的球放入篮子里； 3． 如果颜色为 $x+k$ 的球不在篮子里，将一颗颜色为 $x+k$ 的球放入篮子里。

经过任意多次操作后，小R想知道篮子里的球的颜色集合有多少种可能。输出答案模 $M\left(10^{8} \leq M \leq 10^{9}\right)$ 。

【输入格式】 从文件 basket．in 中读入数据。 本题多侧，第一行一个正整数 $T$ 表示数据组数。 每组数据一行三个正整数 $N, K, M$ 。

【输出格式】 从文件 basket．in 中读入数据。 每组数据输出一行，表示答案。

【样例1输入】

5
4 1 998244353
7 3 998244353
10 4 702443618
18 7 208992811
124 45 678901234

【样例1输出】

7
61
312
128832
256109226

【数据范围与提示】

对于100％的数据，$T \leq 10,2 \leq N \leq 200,1 \leq K \leq 200,10^{8} \leq M \leq 10^{9}$

特殊性质 A：$M=998244353$ 特殊性质 B：$K=2$ 特殊性质 C：$K$ 是偶数

附加文件