# 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

wange2014

## Source

BestCoder Round #80