Segment

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

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.

Sample Input

1 2 107

Sample Output

0

Hint

wange2014

Source

BestCoder Round #80

提交代码