$\ \ \ \ $Silen August does not like to talk with others.She like to find some interesting problems.
$\ \ \ \ $Today she finds an interesting problem.She finds a segment $x+y=q$.The segment intersect the axis and produce a delta.She links some line between $(0,0)$ and the node on the segment whose coordinate are integers.
$\ \ \ \ $Please calculate how many nodes are in the delta and not on the segments,output answer mod P.
Input
$\ \ \ \ $First line has a number,T,means testcase number.
$\ \ \ \ $Then,each line has two integers q,P.
$\ \ \ \ q$ is a prime number,and $2 \le q\le 10^{18},1 \le P \le 10^{18},1 \le T \le 10.$
Output
$\ \ \ \ $Output 1 number to each testcase,answer mod P.
