Inverse
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 562 Accepted Submission(s): 214
Problem Description
In the case of moduling a prime number P, A is called multiplicative inverse of B if and only if A * B ¡Ô 1 (mod P)(0 < A, B < P), now it is a quite simple question: give you B and a prime number P,you should found that A describe above.
Input
The first line contains a single integer T, indicating the number of test cases.
Each test case begin with two integer B and P (1 <= B < P <= 5000).
Each test case begin with two integer B and P (1 <= B < P <= 5000).
Output
For each test case output the answer.
Sample Input
1 5 7
Sample Output
3