题目描述

如果无向图 $G$ 中没有重边与自环，则称 $G$ 是一张简单无向图。

对于无向图 $G$ 中任意一个点 $u$，与 $u$ 相连的边的条数称为 $u$ 的度数。

对于一张有 $n$ 个点的图 $G$，如果 $G$ 中的每个点都有其编号，并且编号构成 $1 \sim n$ 的排列，则称 $G$ 是一张带标号图。

如果带标号简单无向图 $G$ 中每个点的度数的奇偶性均相同，则称 $G$ 是一张好图。

给定正整数 $n$，请你求出恰好包含 $n$ 个点的好图的数量。由于答案可能很大，你只需要输出答案对给定整数 $m$ 取模的结果。

对于两张有 $n$ 个点的好图 $G_1, G_2$，如果存在 $1\leq u < v\leq n$ 使得其中一张图包含边 $(u, v)$ 而另一张图不包含边 $(u, v)$，则认为 $G_1, G_2$ 是不同的。

输入格式

本题测试点包含多组数据。

第一行，一个正整数 $T$（$1\leq T\leq 10^4$），表示数据组数。

对于每组数据：一行，两个正整数 $n, m$（$1\leq n\leq 10^9$，$1\leq m\leq 10^9$），分别表示图的点数和模数。

输出格式

对于每组数据，输出一行，一个整数，表示恰好包含 $n$ 个点的好图的数量对 $m$ 取模的结果。

样例

输入

5
1 2
2 3
3 5
5 63
8 1000000

输出

1
2
2
1
194304

说明

对于 $n=1$，图中仅有点 $1$，无法连边。此时这张图是好图，答案为 $1$。

对于 $n=2$，无论图中有没有边连接点 $1$ 与点 $2$，得到的图都是好图。因此答案为 $2$。