Một số nguyên dương \(X\) được gọi là số đặc biệt nếu \(X\) chia hết cho tổng các chữ số của nó.
Ví dụ số \(1, 9, 10, 12, 18\) là các số đặc biệt, còn số \(13, 15\) không phải là số đặc biệt.

Định nghĩa \(f^1(X)\) là số đặc biệt nhỏ nhất lớn hơn \(X\), \(f^2(X)\) là số đặc biệt nhỏ nhất lớn hơn \(f^1(X), \dots, f^K(X)\) là số đặc biệt nhỏ nhất lớn hơn \(f^{K-1}(X)\).

Một cách hình thức: \(f^K(X) = f^1(f^{K-1}(X))\) với \(K > 1\).

Yêu cầu: Cho hai số nguyên dương \(X, K\), hãy tìm \(f^K(X)\).

Input

• Dòng đầu chứa số nguyên dương \(T\) là số bộ dữ liệu (\(T \le 10^3\)).
• \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(X, K\) (\(X, K \le 10^{12}\)).

Output

• Gồm \(T\) dòng, mỗi dòng là kết quả tương ứng với dữ liệu vào.

Example

3
9 2
1 11
2025 2026

12
18
15519

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(X \le 10^9\); \(K \le 10^3\); \(T = 1\).
• Subtask \(2\) (\(20\%\) số điểm): \(X \le 10^9\); \(K \le 10^7\); \(T = 1\).
• Subtask \(3\) (\(30\%\) số điểm): \(X \le 10^9\); \(K \le 10^9\); \(T = 1\).
• Subtask \(4\) (\(20\%\) số điểm): Không có ràng buộc nào thêm.