Problem Description

$\ \ \ \ $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.

1
2 107

0