#P7223. [2023省队模拟]树
[2023省队模拟]树
题目描述
有一个包含 个顶点、 条边的无向图。其中 个顶点在同一个环上,另有一个顶点在环的中心。环上每对相邻顶点之间有边,每个环上顶点与中心顶点之间也有边。
求该图的生成树数量。两棵生成树视为相同,当且仅当顺时针旋转环若干步后,其中一棵与另一棵相同。旋转保持中心顶点不变。
答案对 取模, 不一定为质数。例如 时,共有 种生成树。
输入格式
第一行一个整数 ,表示数据组数。
接下来 行,每行两个整数 ,分别表示环上的顶点数和模数。
输出格式
每组数据输出一行,表示答案。
样例输入
3
3 233
4 233
4 10
样例输出
6
13
3
数据范围与约定
对于所有数据,,,。
对于 的数据,。对于 的数据,。对于另外 的数据, 互质,且 。