Alice ได้ออกแบบระบบเข้ารหัสลับระบบหนึ่ง โดยจะเข้ารหัสข้อความต้นฉบับเป็นจำนวนเต็มแบบไม่มีเครื่องหมายขนาด 64 บิต $x$ และสุ่มเลือกจำนวนเต็มแบบไม่มีเครื่องหมายขนาด 64 บิต $a$ เป็นกุญแจสาธารณะ จากนั้นเข้ารหัสข้อความต้นฉบับเพื่อให้ได้ข้อความรหัสลับ $b = a^x \bmod 2^{64}$ โดยเฉพาะอย่างยิ่ง กำหนดให้ $0^0 = 1$

ตอนนี้ Bob ดักจับชุดข้อมูลที่ถูกเข้ารหัสได้ $n$ ชุด คือ $(a_i, b_i)$ ($i = 1, 2, \dots, n$) เพื่อที่จะถอดรหัสข้อมูลทั้งหมด สำหรับข้อมูลที่ถูกเข้ารหัสแต่ละชุด Bob จำเป็นต้องหาจำนวนเต็ม $x_i$ ที่เล็กที่สุด ($0 \le x_i < 2^{64}$) ที่ทำให้ $a_i^{x_i} \equiv b_i \pmod{2^{64}}$ หรือระบุว่าข้อมูลนั้นเสียหายไปแล้ว (กล่าวคือ ไม่มี $x_i$ ที่สอดคล้องกับเงื่อนไข) โปรดเขียนโปรแกรมเพื่อช่วย Bob ทำภารกิจนี้ให้สำเร็จ

ข้อมูลนำเข้า

บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม $n$ ($1 \le n \le 10^5$) แทนจำนวนข้อความ

อีก $n$ บรรทัดถัดไป บรรทัดที่ $i$ ประกอบด้วยจำนวนเต็มสองจำนวน $a_i$ และ $b_i$ ($0 \le a_i, b_i < 2^{64}$) แทนกุญแจสาธารณะและข้อความรหัสลับของข้อมูลชุดที่ $i$ ตามลำดับ

ข้อมูลส่งออก

แสดงผล $n$ บรรทัด สำหรับบรรทัดที่ $i$:

• หากมี $x_i$ อย่างน้อยหนึ่งค่าที่สอดคล้องกับเงื่อนไขที่ระบุในโจทย์ ให้แสดงค่าที่เล็กที่สุด
• มิฉะนั้น ให้แสดงบรรทัดที่มีข้อความ broken message

ตัวอย่าง

ข้อมูลนำเข้า

5
2 4
3 27
1000000007 998244353
4 2
1000000007 1000000009

ข้อมูลส่งออก

2
3
994996658310742016
broken message
broken message