指数方程1

题目描述

回答$T$组询问，每次给一个数$a, b, m$，输出最小的非负整数$x$满足$a^x \equiv b \pmod {m}$。

输入格式

第一行一个整数$T$。接下来$T$行，每行三个整数$a, b, m$。

输出格式

一个整数，表示最小的非负整数解，如果无解，输出-1。

样例输入

4
3 7 10
688720331 114514 998244353
5 114514 998244353
688720331 407057022 998244353

样例输出

3
-1
271880075
123

数据范围

对于所有数据，保证$T\leq 100, 1\leq a,b < m \leq 10^9$，保证$a$与$m$互质。