You are given three integers p,a,bp,a,b, where pp is a prime number and p−1p−1 only has prime factors 22 and/or 33. Please find the minimum positive integer xx such that ax≡b(modp)ax≡b(modp).
Input
The first line contains an integer TT indicating there are TT tests. Each test consists of a single line containing three integers: p,a,bp,a,b.
* T≤200T≤200
* 65537≤p≤101865537≤p≤1018
* the prime factors of p−1p−1 can only be 22 or 33
* 2≤a,b≤p−1
Output
For each test, output a line containing an integer xx, representing the minimum positive value such that ax≡b(modp)ax≡b(modp). If there didn't exist any such number xx, please output −1−1.