Alice đã thiết kế một hệ mật mã: hệ thống mã hóa bản rõ thành một số nguyên không dấu 64-bit $x$, và chọn ngẫu nhiên một số nguyên không dấu 64-bit $a$ làm khóa công khai, sau đó mã hóa bản rõ để thu được bản mã $b = a^x \bmod 2^{64}$. Đặc biệt, quy ước rằng $0^0 = 1$.

Bây giờ, Bob đã chặn thu được $n$ bộ thông tin đã mã hóa $(a_i, b_i)$ ($i = 1, 2, \dots, n$). Để giải mã toàn bộ thông tin, với mỗi bộ thông tin đã mã hóa, Bob cần tìm số nguyên nhỏ nhất $x_i$ ($0 \le x_i < 2^{64}$) sao cho $a_i^{x_i} \equiv b_i \pmod{2^{64}}$, hoặc xác định rằng thông tin đó đã bị hỏng (tức là không tồn tại $x_i$ nào thỏa mãn điều kiện). Hãy viết một chương trình giúp Bob hoàn thành nhiệm vụ này.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 10^5$), biểu thị số lượng thông điệp.

Trong $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $a_i$ và $b_i$ ($0 \le a_i, b_i < 2^{64}$), lần lượt biểu thị khóa công khai và bản mã của bộ thông tin thứ $i$.

Kết quả

In ra $n$ dòng, với dòng thứ $i$:

• Nếu tồn tại ít nhất một giá trị $x_i$ thỏa mãn điều kiện nêu trong đề bài, hãy in ra giá trị nhỏ nhất;
• Ngược lại, in ra một dòng broken message.

Ví dụ

Dữ liệu vào

5
2 4
3 27
1000000007 998244353
4 2
1000000007 1000000009

Kết quả

2
3
994996658310742016
broken message
broken message