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