TIN NHẮN BÍ MẬT

Tèo nhận thấy việc trao đổi thông tin giữa các máy tính hiện nay chưa thực sự hiệu quả nên đã tự thiết kế 1 phương thức mã hóa tin nhắn cho riêng mình.

Quy trình mã hóa một số nguyên X được thực hiện như sau:

• Đầu tiên, chọn ra 2 số nguyên tố liên tiếp p_1 và p_2.
• Tính $phi = (p_1 - 1) * (p_2 - 1)$.
• Chọn một số nguyên $A \in [2, phi)$.
• Khi đó, $key = phi$ $mod$ $A$.
• Mã hóa số X thành số Y bằng phép toán $Y = X \oplus key$.

Tèo đã cho bạn của mình biết trước số p_1, do đó khi gửi dữ liệu, Tèo chỉ gửi 3 số N (tích của p_1 và p_2), A và Y. Tèo tin rằng chỉ với 3 thông số này và số p_1 đã gửi từ trước, bạn của Tèo có thể dễ dàng giải mã để tìm lại số X.

Tèo cho rằng phương thức mã hóa của mình rất bảo mật nên đã mang bài toán này đến kỳ thi Team Coding và thách đố mọi người có thể tìm ra số X chỉ từ $N, \ A, \ Y$. Bạn hãy thử tìm lời giải cho câu đố của Tèo nhé!

Đầu vào:

• Dòng đầu tiên chứa số nguyên dương T là số lượng bộ test. $(1 \le T \le 20)$
• T dòng tiếp theo, mỗi dòng là một bộ test gồm 3 số nguyên $N, A, Y$ như đã mô tả ở trên.
  • $(6 \le N < 10^{16})$
  • $(2 \le A < 10^{16}, \ 2 \le Y < 2^{54})$
• Dữ liệu đảm bảo luôn tồn tại đáp án.

Đầu ra:

• Gồm T dòng, mỗi dòng in ra số X tương ứng của từng bộ test.

Ví dụ 1:

Đầu vào:

1
77 23 36

Đầu ra:

42