K. Divisibility
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given three integers $$$a$$$, $$$b$$$ and $$$d$$$, find minimum non-negative integer k such that:

  • $$$a.b^k$$$ is divisible by $$$d$$$
  • $$$a+(b.k)$$$ is divisible by $$$d$$$

If such number doesn't exist print $$$-1$$$.

You have to answer $$$t$$$ independent test cases.

Input

The first line contains one integer $$$t$$$ ($$$ 1 \le t \le 10^5$$$) — the number of queries.

Then q lines follow, each containing three integer $$$a_i, b_i$$$ and $$$d_i (1 \le a_i,b_i,d_i \le 10^9)$$$

Output

For each query print one integer: the answer to this query.

If the answer does not exist, print $$$-1$$$.

Example
Input
6
12 1 4
2 6 12
4 2 8
2 4 8
9 3 27
2 6 64
Output
0
-1
2
-1
6
21