Đức vừa phát minh ra một phép toán cộng độc đáo và đặt tên cho nó là “cộng một kiểu Đức”, cách cộng như sau: Mỗi lần cộng một số nguyên cho một thay vì tăng giá trị của số đó lên một đơn vị Đức lại tăng tất cả các chữ số của số đó lên một đơn vị.

Ví dụ 1: \(15\) “cộng một kiểu Đức” sẽ cho kết quả là \(26\).

Ví dụ 2: \(91\) “cộng một kiểu Đức” sẽ cho kết quả là \(102\).

Yêu cầu: Với \(T\) số nguyên dương \(N\) cho trước hãy tính toán và cho biết sau khi thực hiện \(K\) lần phép cộng một kiểu Đức thì kết quả sinh ra có bao nhiêu chữ số. Vì câu trả lời có thể rất lớn do đó hãy in ra kết quả sau khi chia lấy dư cho \(10^9+7\).

Input

• Dòng thứ nhất: chứa số nguyên \(T\ (1 \leq T \leq 2\cdot 10^5)\).
• \(T\) dòng tiếp theo mỗi dòng chứa 2 số nguyên lần lượt là \(N\) và \(K\) \((1 \leq N \leq 10^9; 1 \leq K \leq 2\cdot 10^5)\).

Output

• Với mỗi trường hợp in ra số lượng chữ số của kết quả chia lấy dư cho \(10^9+7\).

Scoring

• Có \(30\%\) số test với \(T \leq 10, K \leq 20\).
• Có \(20\%\) số test với \(T \leq 100, K \leq 50\).
• Có \(50\%\) số test không có giới hạn gì thêm.

Example

2
9812 2
9899 3

6
8