Problem: 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

Solution (in PYTHON):

Solution:
t=int(raw_input())
while t>0:
	n,m=map(int,raw_input().split())
	s=str(n)
	visited=[]
	while m>0:
		if s in visited:
			j=visited.index(s)
			s=visited[j+((m)%(len(visited)-j))]
			break
		sm=0
		visited.append(s)
		for i in s:
			sm+=int(i)**2
		s=str(sm)
		m-=1
	print s
	t-=1