Ta nhận thấy rằng với \(n\) lớn, các chữ số cuối cùng của \(n!\) luôn có dạng \(\dots \overline{d_k d_{k-1} \dots d_2 d_1 00 \dots 00}\), với \(d_1 \neq 0\). Hãy tìm các chữ số \(d_k, d_{k-1}, \dots, d_2, d_1\) ở trên.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(T\) (số lượng test cases) và \(k\) (số lượng chữ số cần tìm).
• Dòng thứ hai chứa \(T\) số nguyên dương \(n_1, n_2, \dots, n_T\) là các test case.

Output

• Một dòng duy nhất chứa \(T\) xâu, xâu thứ \(i\) gồm \(k\) chữ số \(\overline{d_k d_{k-1} \dots d_2 d_1}\) viết liền kề, mỗi xâu cách nhau bằng một khoảng trắng.

Constraints

• \(T = 5\)
• Subtask \(1\) (\(10\%\)): \(n \leq 10^6, k = 1\)
• Subtask \(2\) (\(20\%\)): \(n \leq 10^6, k = 6\)
• Subtask \(3\) (\(35\%\)): \(n \leq 10^{18}, k = 1\)
• Subtask \(4\) (\(25\%\)): \(n \leq 10^{18}, k = 6\)
• Subtask \(5\) (\(10\%\)): \(n \leq 10^{18}, k = 9\)

Example

4 2
10 11 12 13

88 68 16 08