Chuỗi GCD

Trong một buổi họp chiến lược kinh doanh, FullHouse Dev được đối tác đưa ra một bài toán thú vị về xử lý chuỗi nhị phân. Với kinh nghiệm trong việc xử lý dữ liệu, nhóm đã bắt tay vào phân tích và giải quyết bài toán này.

Bài toán

Cho \(P\) là một chuỗi nhị phân có độ dài \(N\). Đị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 độ 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\) ở hệ cơ số 2.

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à giá trị \(val(GCD(a,b))\) cho 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ả ở hệ cơ số 2 cho bốn test case đầu tiên như sau:

• Test case 1: 100 (hệ nhị phân) = 4 (hệ thập phân)
• Test case 2: 101 (hệ nhị phân) = 5 (hệ thập phân)
• Test case 3: 10101 (hệ nhị phân) = 21 (hệ thập phân)
• Test case 4: 1000100010 (hệ nhị phân) = 546 (hệ thập phân)