指数方程2

题目描述

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

输入格式

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

输出格式

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

样例输入

3
2 0 1024
123 456 789
114514 1919810 504289861

样例输出

10
49
2

数据范围

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