Naot là một người vô cùng yêu thích món trà sữa, một thức uống lâu đời với hương thơm thanh nhã đặc trưng của trà và vị ngọt béo thơm ngon của sữa. Dù tròn vị yêu thương, thơm ngon tròn vị là thế; nhưng trà sữa lại không tốt cho sức khỏe, thức uống này mang quá nhiều năng lượng; do đó Naot phải rất hạn chế sử dụng loại thức uống yêu thích này.

Theo một nghiên cứu gần đây được đăng trên tạp chí một khoa học không chính thống, nếu tổng lượng calo trà sữa tiêu thụ chia hết cho ~n~, ta có thể coi như chưa từng uống trà sữa. Đọc được nghiên cứu này, Naot lập tức muốn biết liệu ông có bao nhiêu cách để uống trà sữa mà có thể coi như chưa từng uống.

Cụ thể, ông uống trà sữa liên tục trong ~k~ ngày; mỗi ngày ông mua về ~n~ cốc trà sữa có hàm lượng calo lần lượt là ~1,2,3,...,n~; mỗi cốc trà sữa mua về có thể uống hoặc không. Ông muốn tính xem có bao nhiêu cách uống trà sữa mà sau ~k~ ngày, có thể coi như ông chưa từng uống trà sữa.

Yêu cầu: Bạn hãy giúp Naot tính số lượng cách nhé, vì đáp án có vẻ rất lớn, hãy in ra số cách chia dư cho ~5600748293801~.

Input

Dòng đầu tiên gồm một số nguyên dương t (~1\le t \le 10~) - Số bộ test cần giải trong bài toán này.

Mỗi bộ test gồm một dòng duy nhất chứa ~2~ số nguyên dương lần lượt là ~n~ và ~k~ (~1\le n\le 10^{12}, 1\le k \le 10^{18}~).

Dữ liệu đảm bảo tổng của ~n~ trong tất cả bộ test không quá ~10^{12}~.

Output

Với mỗi bộ test, in ra trên một dòng là kết quả của bài toán chia dư cho ~5600748293801~.

Subtask

• ~10\%~ số test có ~t=1, n \cdot k \leq 20~.

• ~20\%~ số test khác có ~n, k \le 500~.

• ~20\%~ số test khác có ~n \le 1000~.

• ~30\%~ số test khác có ~n \le 10^6~.

• Số test còn lại không có ràng buộc gì thêm.

Sample Input 1

5
5 1
6 1
3 2
2 5
6 2

Sample Output 1

8
12
24
512
688

Notes

Trong bộ test đầu tiên, các cách uống tà tưa thỏa mãn là: ~\{\}, \{2, 3\}, \{1, 4\}, \{1, 2, 3, 4\}, \{5\}, \{2, 3, 5\}, \{1, 4, 5\}, \{1, 2, 3, 4, 5\}~

Trong bộ test thứ hai, các cách uống trà sữa thỏa mãn là:

~\{\}~

~\{1, 2, 3\}~

~\{2, 4\}~

~\{1, 5\}~

~\{1, 2, 4, 5\}~

~\{3, 4, 5\}~

~\{6\}~

~\{1, 2, 3, 6\}~

~\{2, 4, 6\}~

~\{1, 5, 6\}~

~\{1, 2, 4, 5, 6\}~

~\{3, 4, 5, 6\}~