package main
import "fmt"
import "bufio"
import "os"

var reader=bufio.NewReader(os.Stdin)
var writer=bufio.NewWriter(os.Stdout)

// exgcd 给定正整数a,b，存在x,y，使其满足`a*x+b*y=gcd(a,b)`, 
// 扩展欧几里得算法 `x=y′,y=x′−⌊a/b⌋∗y′`，其中 x′和y′满足为 b,a%b的解。
// 故递归求解即可。
// base case 当 `b=0` 时 `ax+by=a` 故而 `x=1,y=0`。
// 
// 证明过程参考： https://www.acwing.com/solution/content/1393/
func exgcd(a,b int) (x,y,d int){
    if b==0{
        return 1,0,a
    }
    x,y,d=exgcd(b,a%b)
    return y, x - (a/b)*y,d
}

// 已知a,b,m求x, 满足`a∗x≡b(mod m)`，其等价于 `a*x=b-m*y`，因此线性同余方程等价为 `a∗x+m∗y=b`; 
// 根据 Bezout 定理，上述等式有解当且仅当 `gcd(a,m)|b`
// 因此用扩展欧几里得算法求出一组整数 `x′,y′`, 使得 `a∗x′+m∗y′=gcd(a,m)`。 
// 然后 `x=(x′∗ b/gcd(a,m))%m`即是所求。
func main(){
    var n int
    fmt.Fscan(reader, &n)
    var a,b,m int
    for i:=0;i<n;i++{
        fmt.Fscan(reader, &a,&b,&m)
        x,_,d:=exgcd(a,m)
        if b%d>0{
            fmt.Fprintln(writer,"impossible")
        }else{
            fmt.Fprintln(writer, (x*b/d)%m)
        }
    }
    writer.Flush()
}