Many problems require printing the probability of something. Moreover, it is common that if the answer is abab, you should output a×b−1(modp)a×b−1(modp) (pp is a prime number). In these problems, you cannot know the exact value of the probability. It's so confusing!!! Now, we want to reverse engineer the exact probability from such calculated output value xx. We do so by guessing the probability is the one with the minimum bb such that a×b−1=x(modp)a×b−1=x(modp). Now we invite you to solve this problem with us!
You are given two positive integers pp and xx, where pp is a prime number.
Please find the smallest positive integer bb such that there exist some positive integer aa satisfying a<ba<b and a≡bx(modp)a≡bx(modp).
Input
The first line contains an integer TT indicating there are TT tests. Each test consists of a single line containing two integers: p,xp,x.
* 1≤T≤2×1051≤T≤2×105
* 3≤p≤10153≤p≤1015
* pp is a prime
* 1<x<p
Output
For each test, output a line containing a string represents the fraction abab using the format "a/b" (without quotes).