صممت 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