Độ khó: Dễ (1/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Cho ba số ~a~, ~x~, ~y~. Nhiệm vụ của bạn là tìm ước số chung lớn nhất của hai số ~P~ và ~Q~, trong đó ~P~ lặp lại ~x~ lần số ~a~ và ~Q~ lặp lại ~y~ lần số ~a~. Ví dụ ~a = 2~, ~x = 3~, ~y = 2~ thì ~P = 222~, ~Q = 22~.

Dữ liệu vào

• Dòng đầu tiên đưa vào ~T~ là số lượng bộ test.
• ~T~ dòng tiếp theo đưa các bộ test. Mỗi bộ test được viết trên một dòng là bộ ba số ~a~, ~x~, ~y~ phân biệt nhau bởi một vài khoảng trống.

Kết quả

• Đưa ra kết quả mỗi test theo từng dòng.

Giới hạn

• ~1 \le T \le 100~; ~1 \le a, x, y \le 10^{18}~.
• Dữ liệu đảm bảo ~\gcd(x, y) \le 1000~ (để kết quả không quá dài).

Sample Input 1

2
2 2 3
123 5 2

Sample Output 1

2
123

Giải thích

• Test 1: ~a = 2~, ~x = 2~, ~y = 3~ ⇒ ~P = 22~, ~Q = 222~. ~\gcd(22, 222) = 2~ (vì ~22 = 2 \cdot 11~, ~222 = 2 \cdot 3 \cdot 37~) ⇒ in 2.
• Test 2: ~a = 123~, ~x = 5~, ~y = 2~ ⇒ ~P = 123123123123123~, ~Q = 123123~. ~\gcd(P, Q) = 123~ ⇒ in 123.