Cho công thức truy hồi như sau:

Ở đây minDigit(x) và maxDigit(x) là giá trị nhỏ nhất và lớn nhất của chữ số trong x mà không có số 0 ở đầu.

Nhiệm vụ của bạn là tính a_K biết a₁ và K.

Đầu vào

Dòng đầu là số nguyên t (1 <= t <= 1000) là số testcases.

Với mỗi testcase  trên một dòng chưa hai số nguyên a₁ và K (1 <= a₁ <= 10¹⁶, 1 <= K <= 10¹⁶)

Đầu ra 

Mỗi dòng là một số nguyên a_K