给定两个正整数 $N,M$，你需要对于每个 $n=1,\ldots,N$，求解以下问题：

求有多少个长度为 $n$，且每个元素都是 $1\sim n$ 之间正整数的序列 $a$ 满足：

存在至少一个 $i$，满足 $a_i=|\{a_j\mid 1\leq j\leq i\}|$，即 $a_i$ 恰好为 $a_1,\cdots,a_i$ 这些数中不同数的个数。
答案对 $M$ 取模。

输入格式

本题有多组数据。第一行一个正整数 $T$（$1\leq T\leq 75$），表示数据组数。

对于每组测试数据，第一行输入两个整数 $N,M$（$1\leq N\leq 300$，$2\leq M\leq 10^9$）。

保证 $\sum N^3\leq 5\cdot 10^7$。

输出格式

对于每组测试数据，输出一行 $N$ 个整数，表示 $n=1,\ldots,N$ 时的方案数对 $M$ 取模的结果。

样例

输入

1
4 998244353

输出

1 2 16 153