問題ヴィジュアル

イントロダクション

全ての重圧から開放された鳥は, 身につけていた羽を捨てて飛び立っていく...

問題文

$P$ を素数とする.

各要素が整数である $2$ 次正方行列 $A = \begin{pmatrix} A_{1,1} & A_{1,2} \\ A_{2,1} & A_{2,2} \end{pmatrix}, B = \begin{pmatrix} B_{1,1} & B_{1,2} \\ B_{2,1} & B_{2,2} \end{pmatrix}$ が与えられる. $$A^N \equiv B \pmod{P}$$ となる非負整数 $N$ は存在するか? 存在するならば, その中で最小である非負整数 $N$ を求めよ.

ただし, $A^0$ は $2$ 次単位行列であると定義する.

$T$ 個のテストケースについて答えよ.

注記

各要素が整数であるような $2$ つの $2$ 次正方行列 $X=\begin{pmatrix} X_{1,1} & X_{1,2} \\ X_{2,1} & X_{2,2} \end{pmatrix}, Y=\begin{pmatrix} Y_{1,1} & Y_{1,2} \\ Y_{2,1} & Y_{2,2} \end{pmatrix}$ に対して, $$X_{1,1} \equiv Y_{1,1} \pmod{P}, \quad X_{1,2} \equiv Y_{1,2} \pmod{P}, \quad X_{2,1} \equiv Y_{2,1} \pmod{P}, \quad X_{2,2} \equiv Y_{2,2} \pmod{P}$$ の全てが成り立つ時, そしてそのときに限り $X \equiv Y \pmod{P}$ と書く.

なお, この問題の制約下では, 任意の非負整数 $N$ について, $A^N$ は各要素が整数である $2$ 次正方行列になることが証明できる.

制約

• $1 \leq T \leq 5$.
• 各テストケースに対する制約
• $2 \leq P \leq 3 \times 10^5$
• $P$ は素数である.
• $0 \leq A_{i,j} \lt P \quad (i \in \{1,2\}, j \in \{1,2\})$
• $0 \leq B_{i,j} \lt P \quad (i \in \{1,2\}, j \in \{1,2\})$
• 入力は全て整数である.

入力

$T$
$\mathrm{Testcase}_1$
$\mathrm{Testcase}_2$
$\vdots$
$\mathrm{Testcase}_T$

各テストケースは以下の形式である.

$P$
$A_{1,1}$ $A_{1,2}$
$A_{2,1}$ $A_{2,2}$
$B_{1,1}$ $B_{1,2}$
$B_{2,1}$ $B_{2,2}$

出力

出力は $T$ 行からなる.

第 $t~(1 \leq t \leq T)$ 行目には $A^N \equiv B \pmod{P}$ となる非負整数 $N$ が存在する場合はそのような最小の非負整数 $N$ を出力し, 存在しないならば -1 と出力せよ.

最後に改行を忘れないこと.

サンプル

3
97
1 3
2 2
25 39
26 38
2
1 0
0 1
0 0
0 0
3
2 0
0 0
1 0
0 0

3
-1
2

2
200003
162435 193492
172878 37660
178621 199780
199289 135336
299993
10896 279378
226758 289189
16396 219907
249049 89986

20150821
20240201