CLEAR  Clear Numbers
English  Vietnamese 
Bom has just found a definition of clear numbers as the following: for each positive integer n, we form another number by summing the squares of the digits of n. We repeat this procedure. If at some step, we obtain the number 1 then n is called a clear number. For example, for n=19, we have:
19 → 82 (= 1^{2} +9^{2}) → 68 → 100 → 1
Thus, 19 is a clear number.
Not all numbers are clear numbers. For example, for n=12, we have:
12 → 5 → 25 → 29 → 85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89 → 145
Bom is very interested in this definition of clear numbers. He issued a challenge to the landlord: given a positive integer n, find S(n), the clear number succeeding n, i.e. S(n) is the minimum clear number greater than n. However, this question is so easy for the landlord that he challenged Bom with another problem: given two positive integers n and m (1 ≤ n, m ≤ 10^{15}), find the number S^{m}(n)=S(S(…S(n) )) which is the m^{th} clear number succeeding n.
Please help Bom to solve the task!
Input
The first line contains t (0 < t ≤ 20) , the number of test cases.
Each line in the next t lines contains two positive integers n and m.
Output
Print t lines, each line contains the result of the corresponding test case.
Example
Input 2 18 1 1 145674807 Output 19 1000000000
Notes
There are 50% of the test cases in which 1 ≤ n, m ≤ 10^{7}.
hide comments
Thcs Ðặng Chánh Kỷ:
20141101 17:21:41
Forget inc(n) 

TNO:
20101219 17:43:31
S(n) is the minimum clear number that is "strictly" greater than n :) 
Added by:  Duc 
Date:  20090716 
Time limit:  0.200s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  VNOI Marathon 2009 Round 2 Problem Setter: Đỗ Đức Đông 