Unfortunately someone has come and eaten the problem statement. Are you good enough to solve it without the statement?

Input
The first line contains T denoting the number of test cases.
The next  T lines describe test cases and contain two integers each: N and M.

Output
For each test case output one integer - answer for the question.

Constraints
T ≤ 1000
1 ≤ N, M ≤ 10^9

Note:
N, M ≤ 1000 for 30% of the test

SAMPLE INPUT
6
28 1
39 1
90 1
15 2
123 2
114514 1919

SAMPLE OUTPUT
68
90
81
40
17
16
for _ in xrange(int(raw_input())):
    n, m = map(int, raw_input().split())
    arr = [sum([int(x)**2 for x in str(n)])]
    arrset = set(arr)
    for x in xrange(m - 1):
        arr.append(sum([int(x)**2 for x in str(arr[-1])]))
        if arr[-1] in arrset:
            # arr.pop()
            break
        arrset.add(arr[-1])
    else:
        print arr[-1]
        continue
    narr, recur = [], None
    for x in xrange(len(arr) - 1):
        if arr[x] == arr[-1]:
            recur = arr[x:-1]
            break
        else:
            narr.append(arr[x])
    assert recur is not None
    if m <= len(narr):
        print narr[m - 1]
    else:
        m -= len(narr) + 1
        print recur[m % len(recur)]