Question:

A number X is said to be magical number for N and M if X satisfies the following equation for N and M:

(N*X) mod M = 1

Your task is to write a program to find the magical for all given pair of N and M.

Input:

• First line consist of total number test cases 'T'.
• Next T lines contain two variable N and M separated by comma.

Output:

For each pair of N and M print magical number X in new line.

Constraints:

• N, M and X are integer numbers.
• N and X are always less than M.
• M is always a prime number.