$\ \ \ \ $Rivendell非常神,喜欢研究奇怪的问题. $\ \ \ \ $今天他发现了一个有趣的问题.找到一条线段$x+y=q$,令它和坐标轴在第一象限围成了一个三角形,然后画线连接了坐标原点和线段上坐标为整数的格点. $\ \ \ \ $请你找一找有多少点在三角形的内部且不是线段上的点,并将这个个数对$P$取模后告诉他.
$\ \ \ \ $第一行一个数T,为测试数据组数.
$\ \ \ \ $接下来每一行两个数$q$,$P$,意义如题目中所示.
$\ \ \ \ q$是质数且$q\le 10^{18},1\le P\le 10^{18},1\le T \le 10$.
$\ \ \ \ $对每组数据,输出点的个数模$P$后的值.
1 2 107
0