Bờm mới tìm được một tài liệu định nghĩa số rõ ràng như sau: Với số nguyên dương ~n~, ta tạo số mới bằng cách lấy tổng bình phương các chữ số của nó, với số mới này ta lại lặp lại công việc trên. Nếu trong quá trình đó, ta nhận được số mới là ~1~, thì số ~n~ ban đầu được gọi là số rõ ràng. Ví dụ, với ~n = 19~, ta có:

~19 \rightarrow 82 \;\left(= 1^{2} +9^{2} \right) \rightarrow 68 \rightarrow 100 \rightarrow 1~

Như vậy, ~19~ là số rõ ràng.

Không phải mọi số đều rõ ràng. Ví dụ, với ~n = 12~, ta có:

~12 \rightarrow 5 \rightarrow 25 \rightarrow 29 \rightarrow 85 \rightarrow 89 \rightarrow 145 \rightarrow 42 \rightarrow 20 \rightarrow 4 \rightarrow 16 \rightarrow 37 \rightarrow 58 \rightarrow 89 \rightarrow 145~

Bờm rất thích thú với định nghĩa số rõ ràng này và thách đố phú ông: Cho một số nguyên dương ~n~, tìm số ~S(n)~ là số rõ ràng liền sau số ~n~, tức là ~S(n)~ là số rõ ràng nhỏ nhất lớn hơn ~n~. Tuy nhiên, câu hỏi đó quá dễ với phú ông và phú ông đã đố lại Bờm: Cho hai số nguyên dương ~n~ và ~m \;(1 \leq n,m \leq 10^{15} )~, hãy tìm số ~S^{m} (n)=S(S(\dots S(n) ))~ là số rõ ràng liền sau thứ ~m~ của ~n~.

Bạn hãy giúp Bờm giải câu đố này nhé!

Input

• Dòng đầu là số ~t (0 < t \leq 20)~ là số bộ dữ liệu.
• ~t~ dòng sau, mỗi dòng chứa ~2~ số nguyên ~n~ và ~m~.

Output

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

Giới hạn

Có ~50\%~ số test với ~1\leq n,m \leq 10^{7}~ .

Sample Input

2
18 1
1 145674807

Sample Output

19
1000000000