Somas Cíclicas Modulares

#153
Made by: Crazynds
256MB
0.3s

Dado um número inicial $X$, você deseja somá-lo a si mesmo repetidas vezes, sempre tomando o resultado módulo M após cada soma.

Mais formalmente:

Você começa com $S₀ = 0$. Depois, para cada $i$ de $1$ até $Y$, calcula-se:

$$ Sᵢ = (Sᵢ₋₁ + X) mod M $$

Note que, conforme as somas continuam, o valor de $Sᵢ$ pode começar a repetir — ou seja, um ciclo se forma.

Seu objetivo é determinar:

  1. O tamanho do ciclo (quantos valores distintos se repetem ciclicamente);
  2. O valor final $Sᵧ$ após realizar exatamente $Y$ somas.

Input

A primeira linha contém um inteiro $T$ representando o número de casos de testes. $(1 ≤ T ≤ 10^4)$

Cada caso de teste contém três inteiros:

X Y M
  • $1 ≤ X ≤ 10^9$
  • $1 ≤ Y ≤ 10^{18}$
  • $2 ≤ M ≤ 10^{18}$

Output

Imprima para cada caso de teste dois valores separados por espaço:

tamCiclo S_Y

Onde:

  • tamCiclo é o comprimento do ciclo,
  • S_Y é o valor da soma em módulo após $Y$ operações.

Obs: É necessário calcular o tamanho do ciclo mesmo que $Y \lt tamCiclo$

Input Example
Output Example 
10
8 72 10
10 50 10
9 68 6
10 21 25
6 84 24
1 43 20
8 1 11
5 18 7
1 28 5
6 23 13

5 6
1 0
2 0
5 10
4 0
20 3
11 8
7 6
5 3
13 8

10
10 49 4
5 63 4
2 6 23
3 44 7
2 97 12
7 44 27
9 78 24
7 89 9
1 3 8
6 87 26

2 2
4 3
23 12
7 6
6 2
27 11
8 6
9 2
8 3
13 2