Mô tả và yêu cầu

Kfib
Dãy Fibonacci được định nghĩa như sau:
0 𝑛ế𝑢 𝑖=0
𝑓(𝑖) = {1 𝑛ế𝑢 𝑖=1
𝑓(𝑖 − 1) + 𝑓(𝑓 − 2) 𝑛ế𝑢 𝑖 > 1
Cho 𝑀, 𝐴, 𝐵 tìm 𝑘 nhỏ nhất mà 𝑓(𝑘) % 𝑀 = 𝐴 và 𝑓(𝑘 + 1) % 𝑀 = 𝐵.

Dữ liệu vào

- Dòng đầu đầu là số 𝑇 là số bộ dữ liệu (𝑇 ≤ 3);
- Tiếp theo là 𝑇 dòng, mỗi dòng chứa 3 số nguyên 𝑀, 𝐴, 𝐵 (0 ≤ 𝐴, 𝐵 < 𝑀; 𝑀 > 0);

Dữ liệu ra

- Gồm 𝑇 dòng, mỗi dòng là kết quả cho bộ dữ liệu tương ứng, nếu không tồn tại 𝑘 ghi -1.
kfib.inp kfib.out
2 0
10 0 1 5
3 2 2

Subtask 1: 𝑀 ≤ 106;
Subtask 2: 𝑀 ≤ 109;