Với một số nguyên dương \(x\), xét phép biến đổi \(x\) thành \(f(x)\) mô tả như sau:

Xét các chữ số trong biểu diễn thập phân của \(x\) từ trái qua phải (từ hàng cao nhất xuống hàng đơn vị). Với mỗi chữ số \(d\) xét đến thì viết ra giá trị \(d \cdot 3\) trong hệ thập phân. Sau khi duyệt hết biểu diễn thập phân của \(x\), dãy chữ số được viết ra tạo thành biểu diễn thập phân của giá trị \(f(x)\).

Yêu cầu: Cho số nguyên không âm \(k\), xét dãy \(a_0, a_1, a_2, ..., a_n\) xây dựng theo quy tắc:

Hãy cho biết giá trị \(a_n\), vì kết quả có thể rất lớn nên chỉ cần đưa ra số dư của phép chia \(a_n\) cho \(123456789\).

Input

• Dòng 1 chứa số nguyên dương \(T \leq 10^5\) là số test
• \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(k, n\) cách nhau bởi dấu cách ứng với một test
• Ràng buộc: \(k \leq 10^9; n \leq 10^5\)

Output

• Ứng với mỗi test, ghi ra một số nguyên duy nhất trên một dòng là số dư của phép chia \(a_n\) cho \(123456789\)

Example

3
1024 2
68 3
1 100000

901836
96121836
29561031