Chuỗi GCD

Trong một nhiệm vụ mới, các anh hùng của FullHouse Dev đang phải đối mặt với một thử thách về xử lý chuỗi nhị phân. Họ cần phải tìm hiểu về mối quan hệ giữa các chuỗi GCD để giải mã một thông điệp bí ẩn. Với tinh thần không lùi bước, FullHouse Dev bắt đầu nghiên cứu vấn đề này.

Bài toán

Cho một chuỗi nhị phân \(P\) có độ dài \(N\). Ta định nghĩa \(P^\infty\) là một chuỗi vô hạn với \(P^\infty[i] = P[i \bmod N]\) (hiểu đơn giản là \(P^\infty\) là sự nối tiếp của \(P\) với chính nó vô số lần).

Định nghĩa chuỗi GCD của hai số nguyên \(a, b\) với \(a \geq b\) là một chuỗi nhị phân có độ dài \(a\) thỏa mãn:

• \(GCD(a,b) = 10^{b-1}\) (1 theo sau bởi \(b-1\) số 0) nếu \(a\) chia hết cho \(b\)
• \(GCD(a,b) = \) \(b\) ký tự đầu tiên của \(P^\infty\) trong trường hợp còn lại

Gọi \(val(s)\) là giá trị của số nguyên được biểu diễn bởi chuỗi nhị phân \(s\) trong hệ cơ số 2. Cho \(T\) cặp số nguyên \(a, b\), tính \(val(GCD(a,b))\) cho mỗi cặp.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case
• Mỗi test case gồm một dòng chứa hai số nguyên \(a, b\)

OUTPUT FORMAT:

• In ra \(T\) dòng, mỗi dòng là kết quả \(val(GCD(a,b))\) tương ứng với mỗi test case

Ràng buộc:

Với tất cả các test:

• \(1 \leq T \leq 10^5\)
• \(1 \leq b \leq a \leq 10^9\)

File 1 (70 điểm):

• \(a \leq 10^3\)

File 2 (30 điểm):

• Không có ràng buộc thêm

Ví dụ

INPUT

5
3 1
3 2
5 2
10 4
100 3

OUTPUT

4
5
21
546
986497880

Giải thích

Kết quả trong hệ nhị phân cho bốn test case đầu tiên như sau:

• Test case 1: 100 (cơ số 2) = 4 (cơ số 10)
• Test case 2: 101 (cơ số 2) = 5 (cơ số 10)
• Test case 3: 10101 (cơ số 2) = 21 (cơ số 10)
• Test case 4: 1000100010 (cơ số 2) = 546 (cơ số 10)