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은 각 암호화된 정보에 대해 $a_i^{x_i} \equiv b_i \pmod{2^{64}}$를 만족하는 가장 작은 정수 $x_i$ ($0 \le x_i < 2^{64}$)를 찾거나, 해당 정보가 손상되었음(즉, 조건을 만족하는 $x_i$가 존재하지 않음)을 판별해야 합니다. Bob이 이 작업을 수행할 수 있도록 돕는 프로그램을 작성하시오.

입력

첫 번째 줄에 메시지의 개수를 나타내는 정수 $n$ ($1 \le n \le 10^5$)이 주어집니다.

다음 $n$개의 줄 중 $i$번째 줄에는 $i$번째 정보의 공개 키와 암호문을 나타내는 두 정수 $a_i$와 $b_i$ ($0 \le a_i, b_i < 2^{64}$)가 주어집니다.

출력

총 $n$개의 줄을 출력합니다. $i$번째 줄에는 다음을 출력합니다:

• 문제에 제시된 조건을 만족하는 $x_i$가 적어도 하나 존재한다면, 그중 가장 작은 값을 출력합니다.
• 그렇지 않다면, 한 줄에 broken message를 출력합니다.

예제

입력

5
2 4
3 27
1000000007 998244353
4 2
1000000007 1000000009

출력

2
3
994996658310742016
broken message
broken message