For her new ICS assignment, Caroline needs to design a program that uses random numbers. However, she discovers that Ms. Dyke has forbidden using any built-in functions! Now, she needs to create a random number generator to make her assignment work. After checking online, she finds that random numbers can be generated using the following function:

\[f(0) = SEED\]

\[ F(N) = (A \times F(N-1) + B) \bmod P \]

Where \(SEED\) is some initial value between \(0\) and \(P-1\) inclusive. After some tinkering she finds that for most values of \(A\), \(B\), and \(P\), the generated numbers quickly fall into a repeating cycle. She’d like to figure out which values of \(A\), \(B\), and \(P\) produce the best results and has enlisted your help to find the average length of a cycle for one set of values.

**Note**: The cycle length for some value of \(SEED\) is defined as smallest value \(N\) for which
\(F(N)\) produces a number already in the sequence. For example, if \(SEED = 1, F(1) = 2, F(2) = 3,\) and \(F(3) = 3\), then the cycle length is \(3\), as \(3\) was already in the sequence. The average length of a cycle is defined as the average of the cycle lengths for every
possible value of \(SEED\).

#### Input Specification

The first line of the input provides the number of test cases, \(T\ (1 \le T \le 100)\). \(T\) test cases follow. Each test case contains 3 integers, \(A, B\), and \(P\ (1 \le A, B, P \le 10^6)\).

For the first \(20\%\) of cases, \(A, B, P \le 10^3\).

#### Output Specification

For each test case, your program should output one real number, rounded to 6 decimal places, the average length of a cycle.

#### Sample Input

```
2
3 2 5
4 5 3
```

#### Sample Output

```
3.400000
3.000000
```

#### Explanation for Sample

In the second test case, if you start with a \(SEED\) of \(0\), then

- \(F(1) = 4(0) + 5 \bmod 3 = 2\)
- \(F(2) = 4(2) + 5 \bmod 3 = 1\)
- \(F(3) = 4(1) + 5 \bmod 3 = 0\)

Since \(0\) is already in the sequence, the cycle length is \(3\). Starting with \(1\) or \(2\) will also result in a cycle length of \(3\), so the average cycle length is \(3\).

## Comments