Help Shashank in calculating the value of $\mbox{S}$, which is given as follows. Since the value of $\mbox{S}$ can be very large, he only wants the last 2 digits of $\mbox{S}$.

$S=1^N+2^N+3^N+\cdots+K^N$

Input Format 

The first line contains an integer $\mathbf{T}$ i.e. number of the test cases. 

The next $\mathbf{T}$ lines will each contain a pair of integers, i.e. $\mbox{K}$ and $N$.  

Output Format 

Print the last two digits of $\mbox{S}$ for each test case in separate lines.  

Constraints 

$1\leq T\leq10^4$ 

$2\leq K\leq10^{16}$ 

$2\leq N\leq10^{16}$  

Sample Input#00  

3
2 2
2 3
3 3

Sample Output#00  

05
09
36

Sample Input#01  

3
5 2
3 4
3 3

Sample Output#01  

55
98
36

Explanation

For the first test case, $1^2+2^2+3^2+4^2+5^2=55$

Difficulty: HARD
Tags: Matrices

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	(k, n) = map(int, input().split())
	k += 1
	full = sum((pow(i, n, 100) for i in range(100))) % 100
	tail = sum((pow(i, n, 100) for i in range(k % 100))) % 100
	ans = (full * (k // 100) + tail) % 100
	print('{:02d}'.format(ans))


def f(k, n):
	m = 100
	(q, r) = (k // m, k % m)
	li = [0] * m
	li[0] = 1
	for i in range(1, len(li)):
		li[i] += (li[i - 1] + pow(i + 1, n, m)) % m
	return (q * li[m - 1] + (0 if r == 0 else li[r - 1])) % m
for _ in range(int(input())):
	print(str(f(*[int(i) for i in input().split()])).zfill(2))


T = int(input())
S = [None] * 40
for _ in range(T):
	(K, N) = (int(_) for _ in input().split())
	N40 = N % 40
	if S[N40] == None:
		S[N40] = [0]
		for i in range(1, 100):
			S[N40].append((S[N40][-1] + pow(i, N40 + 40, 100)) % 100)
	s = (S[N40][99] * (K // 100) + S[N40][K % 100]) % 100
	print('%02d' % s)


def compute_rems(j, N):
	rems = []
	for i in range(1, j + 1):
		rems.append(pow(i, N, 100))
	return rems

def solve(K, N):
	sum100rems = sum(compute_rems(99, N)) % 100
	(q, r) = divmod(K, 100)
	sumOtherRems = sum(compute_rems(r, N)) % 100
	res = (q * sum100rems % 100 + sumOtherRems) % 100
	if res < 10:
		return '0' + str(res)
	else:
		return res
T = int(input())
for _ in range(T):
	(K, N) = map(int, input().split())
	print(solve(K, N))


def comp(x):
	if x == 0:
		return 0
	return (1 + (1 + 4 * x) ** 0.5) / 2

def compute(k, n):
	sa = 0
	for i in range(1, k + 1):
		sa += pow(i, n, 100)
	return sa % 100

def compute2(k, n):
	numx = int((k + 1) / 100) % 100
	if k % 100 == 99:
		return compute(99, n) * numx % 100
	else:
		return (compute(99, n) * numx + compute(k % 100, n)) % 100
tcs = int(input())
for i in range(tcs):
	(a, b) = map(int, input().split(' '))
	ans = compute2(a, b)
	if len(str(ans)) == 1:
		print('0' + str(ans))
	else:
		print(str(ans))


def createLUT():
	global lut
	global lutr
	lut = dict()
	lutr = dict()
	for x in range(0, 101):
		lut[x] = [1]
		p = x
		c = 1
		while c > 0:
			lut[x].append(p % 100)
			p = p * x
			if p % 100 in lut[x]:
				lutr[x] = lut[x].index(p % 100)
				c -= 1
	return lut

def sumOfFirst(i, N):
	sum = 0
	global lut
	global lutr
	for x in range(1, i + 1):
		shift = lutr[x]
		if N < len(lut[x]):
			s = lut[x][N]
		else:
			index = (N - shift) % (len(lut[x]) - shift) + shift
			s = lut[x % 100][index]
		sum += s
	return sum

def solve(K, N):
	sum1 = 0
	if K >= 100:
		sum1 = sumOfFirst(100, N) * (K // 100)
	sum2 = sumOfFirst(K % 100, N)
	return (sum1 + sum2) % 100
createLUT()
for _ in range(0, int(input())):
	print('%02d' % solve(*[int(x) for x in input().split(' ')]))


def binPow(x, a, mod):
	y = 1
	if a > mod:
		a %= mod
		a += mod
	while a > 0:
		if a & 1:
			y *= x
			y %= mod
		x *= x
		x %= mod
		a >>= 1
	return y

def sum(k, n, mod):
	sum = 0
	for i in range(k):
		sum = sum + binPow(i, n, mod)
	return sum % mod
mod = 100
t = int(input())
for i in range(t):
	[k, n] = [int(x) for x in input().split(' ')]
	k = k + 1
	pref = sum(mod, n, mod)
	rem = sum(k % mod, n, mod)
	ans = k // mod * pref + rem
	ans = str(ans % mod)
	if len(ans) < 2:
		ans = '0' + ans
	print(ans)


t = int(input())
for test in range(t):
	s = input().strip().split()
	k = int(s[0])
	n = int(s[1])
	q = k // 100
	r = k % 100
	rem = 0
	for i in range(1, r + 1):
		rem += pow(i, n, 100)
		rem %= 100
	lt = rem
	if q > 0:
		for i in range(r + 1, 100):
			rem += pow(i, n, 100)
			rem %= 100
	ans = (rem * q + lt) % 100
	s = str(ans)
	if len(s) == 1:
		s = '0' + s
	print(s)


t = int(input())
for i in range(0, t):
	temp = input()
	arr = temp.split(' ')
	k = int(arr[0])
	n = int(arr[1])
	sum = 0
	if n % 4 == 0:
		sum = 30 * (k // 100)
	elif n % 2 == 0:
		sum = 50 * (k // 100)
	for j in range(1, k % 100 + 1):
		sum = sum + pow(j, n, 100)
	sum = sum % 100
	if sum >= 10:
		print(sum)
	else:
		print('0' + str(sum))


def powerloop(p, mod):
	(first_appearance, powerlist) = ({}, [])
	for (counter, value) in enumerate(powersUnderMod(p, mod)):
		if value in first_appearance:
			break
		first_appearance[value] = counter
		powerlist.append(value)
	looplength = counter - first_appearance[value]
	leadin = first_appearance[value]
	return (leadin, looplength, powerlist)

def powersUnderMod(p, mod):
	n = 1
	while True:
		yield n
		n = n * p % mod

def makePowerMod(p, mod):
	(leadin, looplength, powerlist) = powerloop(p, mod)

	def powerMod(exp):
		if exp < len(powerlist):
			return powerlist[exp]
		return powerlist[(exp - leadin) % looplength + leadin]
	return powerMod

def powerCalculator(mod):
	return tuple([makePowerMod(p, mod) for p in range(mod)])

def runPowerCalculation(mod=100):
	calc = powerCalculator(mod)
	num_tests = int(input())
	for testnum in range(num_tests):
		(K, exp) = map(int, input().split(' '))
		K += 1
		result = (sum((calc[p](exp) for p in range(K % mod))) + K // mod * sum((calc[p](exp) for p in range(mod)))) % 100
		if result < 10:
			result = '0%d' % result
		print(result, end='')
		if testnum < num_tests - 1:
			print('')
runPowerCalculation()


P = S = {}
for K in range(101):
	P[K, 0] = 1
	for N in range(1, 22):
		P[K, N] = P[K, N - 1] * K % 100
for N in range(22):
	S[0, N] = 0
	for K in range(1, 101):
		S[K, N] = (S[K - 1, N] + P[K, N]) % 100
for _ in range(int(input())):
	(K, N) = map(int, input().split())
	N = min(N, (N - 2) % 20 + 2)
	(Q, R) = divmod(K, 100)
	ans = (Q * S[100, N] + S[R, N]) % 100
	print('%02d' % ans)


def solve(K, N):
	s = sum((pow(i, N, 100) for i in range(100)))
	(d, r) = divmod(K, 100)
	s *= d
	s += sum((pow(i, N, 100) for i in range(r + 1)))
	return s % 100
T = int(input())
for _ in range(T):
	(K, N) = (int(_) for _ in input().split())
	print('%02d' % solve(K, N))


import itertools, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(K, N) = list(map(int, sys.stdin.readline().split()))
	x = list(itertools.accumulate((pow(i, N, 100) for i in range(100))))
	print('%02d' % ((K // 100 * x[-1] + x[K % 100]) % 100))


T = int(input())
for i in range(T):
	(K, N) = [int(x) for x in input().split()]
	unit = sum([pow(i, N, 100) for i in range(1, 100)]) % 100
	rest = sum([pow(i, N, 100) for i in range(1, K % 100 + 1)]) % 100
	res = (unit * (K // 100) + rest) % 100
	print('%02d' % res)


t = int(input())
while t > 0:
	t = t - 1
	y = input()
	x = y.split(' ')
	k = int(x[0])
	n = int(x[1])
	p = (n - 2) % 20
	p = p + 2
	if n > p:
		n = p
	arr = []
	arr.append(0)
	arr.append(1)
	i = 2
	while i <= 100:
		b = i ** n
		b = b % 100
		arr.append((arr[i - 1] + b) % 100)
		i = i + 1
	q = k % 100
	x = int(k / 100)
	sum = (x * arr[100] + arr[q]) % 100
	sum = int(sum)
	r = int(sum / 10)
	if r == 0:
		print('0' + str(sum))
	else:
		print(sum)


import itertools, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(K, N) = list(map(int, sys.stdin.readline().split()))
	x = list(itertools.accumulate((pow(i, N, 100) for i in range(100))))
	print('%02d' % ((K // 100 * x[-1] + x[K % 100]) % 100))


import itertools, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(K, N) = list(map(int, sys.stdin.readline().split()))
	x = list(itertools.accumulate((pow(i, N, 100) for i in range(100))))
	print('%02d' % ((K // 100 * x[-1] + x[K % 100]) % 100))


a_to_n = [0] * 10
a_to_nm1 = [0] * 10
ba_to_n = [0] * 100
for _ in range(int(input())):
	(k, n) = map(int, input().split())
	for a in range(10):
		a_to_nm1[a] = pow(a, n - 1, 100)
		a_to_n[a] = a_to_nm1[a] * a % 100
	for ba in range(100):
		a = ba % 10
		ba_to_n[ba] = ((ba - a) * n * a_to_nm1[a] + a_to_n[a]) % 100
	sum_100 = sum(ba_to_n) % 100
	(segs, left) = divmod(k, 100)
	print(str(segs * sum_100 + sum(ba_to_n[:left + 1]) + 100)[-2:])


nTst = int(input())
th = 100
for i in range(nTst):
	[k1, n1] = list(map(int, input().split()))
	hund = k1 // 100
	resid = k1 % 100
	s1 = 0
	if hund > 0:
		for i1 in range(1, 100):
			s1 = (s1 + pow(i1, n1, th)) % th
	s2 = 0
	if resid > 0:
		for i1 in range(1, resid + 1):
			s2 = (s2 + pow(i1, n1, th)) % th
	s0 = (s1 * (hund % th) + s2) % th
	if s0 < 10:
		print('0', s0, sep='')
	else:
		print(s0)


from itertools import accumulate, count
from functools import reduce
t100 = list((list((r % 100 for r in accumulate((pow(i, N, 100) for i in range(101))))) for N in range(20, 40)))

def clever(K, N):
	return (t100[N % 20][100] * (K // 100) + t100[N % 20][K % 100]) % 100
for _ in range(int(input().strip())):
	(K, N) = list((int(i) for i in input().strip().split()))
	r = clever(K, N)
	if r >= 10:
		print(r)
	else:
		print('0', r, sep='')


import sys

def solve(k, n):
	c100 = k // 100
	r100 = k % 100
	s1 = sum([pow(i, n, 100) for i in range(100)]) % 100
	s2 = sum([pow(i, n, 100) for i in range(r100 + 1)]) % 100
	print('k=%d n=%d c100=%d r100=%d s1=%d s2=%d' % (k, n, c100, r100, s1, s2), file=sys.stderr)
	return (s1 * c100 + s2) % 100
t = int(input())
for _ in range(t):
	(k, n) = map(int, input().split())
	v = solve(k, n)
	print('%02d' % v)


from itertools import accumulate
cumsum = list((list(map(lambda x: x % 100, accumulate((pow(i, j, 100) for i in range(100))))) for j in range(2, 22)))
for _ in range(int(input())):
	(k, n) = map(int, input().split())
	print('{:02d}'.format((cumsum[(n - 2) % 20][k % 100] + k // 100 % 10 * cumsum[(n - 2) % 20][-1]) % 100))


T = int(input())
for t in range(T):
	(K, N) = [int(a) for a in input().split()]
	(k, l) = divmod(K, 100)
	s = 0
	for n in range(1, 100):
		if n % 10:
			s += pow(n, N, 100) * k % 100
	for n in range(1, l + 1):
		if n % 10:
			s += pow(n, N, 100) % 100
	s = s % 100
	if 0 <= s <= 9:
		print('0' + str(s))
	else:
		print(s)


t = int(input())
for _ in range(t):
	(k, n) = map(int, input().split())
	s25r = 0
	e25 = n % 20
	q = k // 25 % 25
	r = k % 25
	for i in range(1, r + 1):
		if i % 5 == 0:
			continue
		s25r += i ** e25 % 25
	s25q = s25r
	for i in range(r + 1, 25):
		if i % 5 == 0:
			continue
		s25q += i ** e25 % 25
	s25 = (s25q * q + s25r) % 25
	s4 = 0
	e4 = n % 2
	if e4 == 0:
		s4 = 2 * (k // 4 % 2)
	for i in range(1, k % 4 + 1, 2):
		s4 += i ** e4
	s4 %= 4
	print('{:02d}'.format((25 * s4 - 24 * s25) % 100))


for _ in range(int(input())):
	(K, N) = map(int, input().split())
	K %= 1000
	if N > 1000:
		N = 1000 + N % 1000
	print('%.2d' % (sum((pow(i, N, 100) for i in range(1, K + 1))) % 100))


cycle_limit = {0: 1, 1: 1, 3: 20, 4: 10, 7: 4, 8: 20, 9: 10, 11: 10, 12: 20, 13: 20, 16: 5, 17: 20, 19: 10, 21: 5, 23: 20, 24: 4, 25: 1, 27: 20, 28: 20, 29: 10, 31: 10, 32: 4, 33: 20, 36: 5, 37: 20, 39: 10, 41: 5, 43: 4, 44: 10, 47: 20, 48: 20, 49: 4, 51: 4, 52: 20, 53: 20, 56: 5, 57: 4, 59: 10, 61: 5, 63: 20, 64: 10, 67: 20, 68: 4, 69: 10, 71: 10, 72: 20, 73: 20, 75: 4, 76: 1, 77: 20, 79: 10, 81: 5, 83: 20, 84: 10, 87: 20, 88: 20, 89: 10, 91: 10, 92: 20, 93: 4, 96: 5, 97: 20, 99: 4}
nocycle = {2: (2, 4), 5: (2, 25), 6: (2, 36), 10: (2, 0), 14: (2, 96), 15: (2, 25), 18: (2, 24), 20: (2, 0), 22: (2, 84), 26: (2, 76), 30: (2, 0), 34: (2, 56), 35: (2, 25), 38: (2, 44), 40: (2, 0), 42: (2, 64), 45: (2, 25), 46: (2, 16), 50: (2, 0), 54: (2, 16), 55: (2, 25), 58: (2, 64), 60: (2, 0), 62: (2, 44), 65: (2, 25), 66: (2, 56), 70: (2, 0), 74: (2, 76), 78: (2, 84), 80: (2, 0), 82: (2, 24), 85: (2, 25), 86: (2, 96), 90: (2, 0), 94: (2, 36), 95: (2, 25), 98: (2, 4)}

def sumlist(p, q, lst):
	res = []
	i = 0
	while i < len(lst):
		res.append(p * lst[i] % 100)
		if i <= q:
			res[-1] = (res[-1] + lst[i]) % 100
		i += 1
	return res

def brutal(k, n):
	s = 0
	for i in range(k + 1):
		s += i ** n % 100
	return s % 100

def smart(k, n):
	ost = 100
	p = k // ost
	q = k % ost
	mnog = [0] * ost
	for j in range(ost):
		if j in cycle_limit:
			if cycle_limit[j] == 1:
				mnog[j] = j
			else:
				mnog[j] = j ** ((n - 1) % cycle_limit[j] + 1) % ost
		else:
			g = j * j % ost
			if g == 0:
				mnog[j] = 0
			elif cycle_limit[g] == 1:
				mnog[j] = g * j ** (n % 2) % ost
			else:
				mnog[j] = g ** ((n // 2 - 1) % cycle_limit[g] + 1) * j ** (n % 2) % ost
	p_list = sumlist(p, q, mnog)
	result = sum(p_list) % ost
	return result
T = int(input())
for i in range(T):
	(K, N) = (int(j) for j in input().split())
	result = smart(K, N)
	print(str(result).zfill(2))


def res(n):
	powers = [0, 1]
	n = n % 40
	for i in range(2, 10):
		p = n
		if i % 2 == 0:
			p = p % 20
			if p < 3:
				p += 20
		if i == 5:
			powers.append(25)
			continue
		powers.append(i ** p % 100)
	return powers
T = int(input())
for i in range(T):
	(K, N) = (int(x) for x in input().split(' '))
	powers = res(N - 1)
	A = sum([powers[b] * 10 * (b + 45 * N) % 100 for b in range(1, 10)])
	x = K % 100 // 10
	B = sum([powers[b] * (b * x + 10 * (x * (x - 1) // 2) * N) % 100 for b in range(1, 10)])
	C = sum([powers[b] * (10 * x * N + b) for b in range(1, K % 10 + 1)])
	m = K // 100 % 100
	print('%02d' % ((m * A + B + C) % 100))


for cas in range(int(input())):
	(k, n) = map(int, input().split())
	calc = 0
	for i in range(100):
		calc = (calc + pow(i, n, 100)) % 100
	rep = k // 100
	rem = k % 100
	extra = 0
	for i in range(rem + 1):
		extra = (extra + pow(i, n, 100)) % 100
	ans = str((rep * calc + extra) % 100)
	if len(ans) == 1:
		ans = '0' + ans
	print(ans)


t = int(input())
for _ in range(t):
	[k, n] = [int(x) for x in input().strip().split(' ')]
	(p, pre) = ([], [])
	for x in range(100):
		p.append(pow(x, n, 100))
	for x in range(100):
		pre.append(p[x] + (pre[-1] if x > 0 else 0))
	tt = k // 100 * pre[99]
	tt = tt + pre[k % 100]
	print('%02.d' % (tt % 100))


for _ in range(int(input())):
	(k, n) = [int(x) for x in input().split()]
	sum = 0
	if k > 100:
		const = 0
		for i in range(1, 100):
			const = (const + pow(i, n, 100)) % 100
		m = k // 100
		r = k % 100
		sum += m * const % 100
		for i in range(1, r + 1):
			sum = (sum + pow(i, n, 100)) % 100
	else:
		for i in range(1, k + 1):
			sum = (sum + pow(i, n, 100)) % 100
	print(str(sum).zfill(2))


def reducepower(k):
	if k > 22:
		if k % 20 < 2:
			return k % 20 + 20
		return k % 20
	return k

def printTwoDigits(n):
	print('0' + str(n) if n < 10 else str(n))
for __ in range(int(input())):
	(K, N) = [int(i) for i in input().split()]
	S = sum([i ** reducepower(N) % 100 for i in range(1, K % 100 + 1)])
	if K > 100:
		S += K // 100 * sum([i ** reducepower(N) % 100 for i in range(1, 101)])
	printTwoDigits(S % 100)


T = int(input())
for i in range(T):
	info = input().split()
	K = int(info[0])
	N = int(info[1])
	K1 = K // 100
	K2 = K % 100
	N1 = N // 100
	N2 = N % 100
	s = 0
	t = 0
	for j in range(1, 101):
		s = (s + pow(j, N, 100)) % 100
	for j in range(1, K2 + 1):
		t = (t + pow(j, N, 100)) % 100
	w = (s * K1 + t) % 100
	if w < 10:
		print('0' + str(w))
	else:
		print(w)


rotate_map = {}
amount_location = 'counter'
for x in range(101):
	rotate_map[x] = {0: 1, 1: x}
	next = x
	current_map = rotate_map[x]
	count = 2
	while next not in current_map:
		current_map[next] = next * x % 100
		next = current_map[next]
	rotate_map[x][amount_location] = next

def pow(base, amount):
	index = 1
	size = len(rotate_map[base]) - 1
	while amount > 0:
		amount -= 1
		size -= 1
		if index == 0:
			return 0
		elif rotate_map[base][amount_location] == index:
			amount %= size
		index = rotate_map[base][index]
	return index

def calc(base, amount):
	total = 0
	m = base // 100
	if m == 0:
		m = 1
	old_base = base % 100 if base > 100 else -1
	if base > 100:
		base = 100
	for x in range(1, base + 1):
		value = pow(x, amount)
		multi = m
		if old_base >= x:
			multi += 1
		total = (total + value * multi) % 100
	return total
testCount = int(input().strip())
for x in range(testCount):
	(base, amount) = [int(i) for i in input().strip().split(' ')]
	print(str(calc(base, amount)).rjust(2, '0'))


import math
for _ in range(0, int(input())):
	(k, n) = map(int, input().split())
	a = [1]
	for u in range(2, 101):
		a.append((pow(u, n, 100) + a[u - 2]) % 100)
	ans = k // 100 * a[99] % 100
	if k % 100 > 0:
		ans = (ans + a[k % 100 - 1]) % 100
	print(str(ans).rjust(2, '0'))


def pwr(base, exp):
	out = 1
	tmp4 = base % 4
	tmp25 = base % 25
	acc4 = 1
	acc25 = 1
	if base == 0:
		return 0
	exp4 = exp
	if base % 2 != 0:
		exp4 = exp4 % 2
		acc4 = base ** exp4 % 4
	elif exp4 >= 2:
		acc4 = 0
	else:
		acc4 = base % 4
	exp25 = exp
	if base % 5 != 0:
		exp25 = exp25 % 20
		k = 0
		while exp25 > 0:
			if exp25 % 2 ** (k + 1) != 0:
				exp25 -= 2 ** k
				acc25 = acc25 * tmp25 % 25
			tmp25 = tmp25 ** 2 % 25
			k += 1
	elif exp25 >= 2:
		acc25 = 0
	else:
		acc25 = base % 25
	return (25 * acc4 - 24 * acc25) % 100
T = int(input())
for i in range(T):
	KN = [int(x) for x in input().split()]
	K = KN[0]
	N = KN[1]
	numsum = K // 100
	extrasum = K % 100
	sextra = sum([pwr(i, N) for i in range(1, extrasum + 1)])
	sextra2 = sum([pwr(i, N) for i in range(extrasum + 1, 100)])
	s100 = sextra + sextra2
	s = (s100 * numsum + sextra) % 100
	if s == 0:
		printifysum = '00'
	elif s < 10:
		printifysum = '0' + str(s)
	else:
		printifysum = str(s)
	print(printifysum)


def cycle(k):
	L = []
	for i in range(100):
		res = k ** i % 100
		for (r, j) in L:
			if res == r:
				return (j, i - j)
		L.append((res, i))

def cycles():
	L = []
	for i in range(100):
		L.append(cycle(i))
	return L

def buildPowerList(cycles, N):
	powerList = []
	for i in range(100):
		pow = N
		if pow >= cycles[i][0] + cycles[i][1]:
			pow = (pow + cycles[i][1] - cycles[i][0]) % cycles[i][1] + cycles[i][0]
		powerList.append(i ** pow % 100)
	return powerList

def sumPowers(powerList, r):
	S = 0
	for i in range(r):
		S += powerList[i]
	return S % 100

def computeSum(powerList, K):
	q = K // 100 % 100
	r = K % 100
	if q > 0:
		S = q * sumPowers(powerList, 100)
	else:
		S = 0
	return (S + sumPowers(powerList, r)) % 100
ctest = int(input())
c = cycles()
for itest in range(ctest):
	(K, N) = list(map(int, input().split()))
	powerList = buildPowerList(c, N)
	print('{:02}'.format(computeSum(powerList, K + 1)))


import itertools
for _ in range(int(input())):
	(K, N) = list(map(int, input().split()))
	x = list(itertools.accumulate((pow(i, N, 100) for i in range(100))))
	print('%02d' % ((K // 100 * x[-1] + x[K % 100]) % 100))


t = int(input())

def power_mod(i, k):
	i = i % 100
	ret = 1
	while k > 0:
		if k & 1 == 1:
			ret = ret * i % 100
		i = i * i % 100
		k >>= 1
	return ret
while t > 0:
	t -= 1
	(k, n) = [int(x) for x in input().split()]
	powers = [power_mod(i, n) for i in range(100)]
	s = sum(powers)
	(q, r) = (k // 100, k % 100)
	ans = (q * s + sum(powers[:r + 1])) % 100
	print('{:02d}'.format(ans))


def value(n, v):
	if n % 100 >= v:
		return n // 100 + 1
	else:
		return n // 100
t = int(input())
for i in range(t):
	l = list(map(int, input().split()))
	k = l[0]
	n = l[1]
	s = 0
	for j in range(1, 100):
		v = value(k, j)
		s += v * pow(j, n, 100) % 100
	print('{:02d}'.format(s % 100))


def f(K, N):
	num = K // 100
	rem = K % 100
	temp = 0
	for i in range(1, 101):
		temp += pow(i, N, 100)
		temp %= 100
	ans = temp * num % 100
	for i in range(1, rem + 1):
		ans += pow(i, N, 100)
		ans %= 100
	if ans == 0:
		return '00'
	elif ans < 10:
		ans = '0' + str(ans)
	else:
		ans = str(ans)
	return ans
for _ in range(int(input())):
	(K, N) = list(map(int, input().strip().split(' ')))
	print(f(K, N))


for _ in range(int(input())):
	(k, n) = [int(a) for a in input().strip().split(' ')]
	sum = 0
	times = k // 100
	rem = k % 100
	unit = 0
	for i in range(1, 101):
		unit += pow(i, n, 100)
		unit %= 100
	for i in range(1, rem + 1):
		sum += pow(i, n, 100)
		sum %= 100
	sum += unit * times
	sum %= 100
	if sum < 10:
		print('0' + str(sum))
	else:
		print(sum)


T = int(input())
for t in range(T):
	(K, N) = map(int, input().split())
	N %= 40
	if N < 2:
		N += 40
	s = 0
	for i in range(100):
		s += pow(i, N, 100)
	s = s * (K // 100) % 100
	for i in range(K % 100 + 1):
		s += pow(i, N, 100)
	print('{:02d}'.format(s % 100))


def S(k, n):
	n = n % 20
	if n == 0:
		n = 20
	elif n == 1:
		n = 21
	q = k // 100
	r = k % 100
	sum1 = 0
	sum2 = 0
	for i in range(1, 100):
		sum1 += pow(i, n) % 100
		if i <= r:
			sum2 += pow(i, n) % 100
	result = (sum1 * q + sum2) % 100
	if result >= 10:
		return str(result)
	else:
		return '0' + str(result)
for i in range(int(input())):
	(k, n) = input().split()
	(k, n) = [int(k), int(n)]
	print(S(k, n))


(PR1, SM1) = (dict(), dict())
for i in range(0, 100):
	for j in range(i, 100):
		(prod, sum1) = (i * j % 100, (i + j) % 100)
		PR1[i, j] = prod
		PR1[j, i] = prod
		SM1[i, j] = sum1
		SM1[j, i] = sum1

def fpm(a, n):
	A = []
	prod = a
	while prod not in A:
		A.append(prod)
		prod = PR1[prod, a]
	l12 = len(A)
	l1 = A.index(prod)
	l2 = l12 - l1
	idx = (n - l1) % l2 - 1
	return A[l1:][idx]
t = int(input().strip())
for _ in range(t):
	(k, n) = map(int, input().strip().split())
	(ansr1, ansr2) = (0, 0)
	(kd, kr) = divmod(k, 100)
	kd %= 100
	for i in range(1, 100):
		ansr1 = SM1[ansr1, fpm(i, n)]
		if i == kr:
			ansr2 = ansr1
	ansr = PR1[ansr1, kd] if kd else 0
	ansr = SM1[ansr, ansr2]
	ansr = str(ansr)
	if len(ansr) < 2:
		ansr = '0' + ansr
	print(ansr)


for i in range(int(input())):
	(k, n) = map(int, input().strip().split(' '))
	kton = []
	for i in range(1, 101):
		kton.append(pow(i, n, 100))
	sum_100 = sum(kton) % 100
	first_sum = k // 100 * sum_100 % 100
	sum_rest = sum(kton[:k % 100])
	first_sum += sum_rest
	last_sum = first_sum % 100
	if last_sum < 10:
		print('0' + str(last_sum))
	else:
		print(last_sum)


import itertools, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(K, N) = list(map(int, sys.stdin.readline().split()))
	x = list(itertools.accumulate((pow(i, N, 100) for i in range(100))))
	print('%02d' % ((K // 100 * x[-1] + x[K % 100]) % 100))


def bitize(x):
	L = []
	while x > 0:
		L.append(x % 2)
		x //= 2
	if not L:
		L = [0]
	return L

def pow_mod(a, b, m):
	b_bits = bitize(b)
	a_powers = [0 for x in b_bits]
	a_powers[0] = a % m
	if b_bits[0]:
		total = a % m
	else:
		total = 1
	for i in range(1, len(b_bits)):
		a_powers[i] = a_powers[i - 1] * a_powers[i - 1] % m
		if b_bits[i]:
			total *= a_powers[i]
			total %= m
	return total

def compute_power_sum(K, N, modulus):
	total = 0
	if N >= 40:
		for i in range(1, 100):
			total += pow_mod(i, N % 40 + 40, 100)
	else:
		for i in range(1, 100):
			total += pow_mod(i, N, 100)
	total %= 100
	total *= K // 100
	total %= 100
	if N >= 40:
		for i in range(1, K % 100 + 1):
			total += pow_mod(i, N % 40 + 40, 100)
	else:
		for i in range(1, K % 100 + 1):
			total += pow_mod(i, N, 100)
	return total % 100
test_cases = int(input())
for i in range(0, test_cases):
	(K, N) = [int(a) for a in input().split()]
	ans = compute_power_sum(K, N, 100)
	if ans < 10:
		print('0' + str(ans))
	else:
		print(ans)


for _ in range(int(input())):
	(k, n) = map(int, input().split())
	phi = 40
	p = n % phi
	if p < 2:
		p += 40
	f = k // 100
	r = k % 100
	sm = 0
	if f > 0:
		sm = sum((i ** p for i in range(1, 101)))
	f %= 100
	ans = (sm * f + sum((i ** p for i in range(1, r + 1)))) % 100
	if ans < 10:
		print(0, ans, sep='')
	else:
		print(ans)


def calc(k, n):
	[q, r] = [k // 100, k % 100]
	s = 0
	for i in range(1, 101):
		s += pow(i, n, 100)
	s %= 100
	ans = q * s % 100
	if r > 0:
		s = 0
		for i in range(1, r + 1):
			s += pow(i, n, 100)
		s %= 100
		ans = (ans + s) % 100
	return ans
T = int(input())
for _ in range(T):
	[K, N] = input().split()
	[K, N] = [int(K), int(N)]
	print('%02d' % calc(K, N))


mod4 = {0: 1, 1: 2, 2: 3, 3: 4}
pow100 = {2: (2, 22), 3: (0, 20), 4: (1, 11), 5: (2, 3), 6: (2, 7), 7: (0, 4), 8: (1, 21), 9: (0, 10)}

def power(k, n):
	if k < 2:
		return k ** n
	elif n == 0:
		return 1
	elif n == 1:
		return k % 100
	elif 1 < k < 10:
		pn = (n - pow100[k][0]) % (pow100[k][1] - pow100[k][0]) + pow100[k][0]
		return k ** pn % 100
	else:
		k1 = k % 10
		k2 = (k - k1) // 10
		k2
		return (power(k1, n) + n * (k - k1) * power(k1, n - 1)) % 100
T = int(input().strip())
for _ in range(T):
	(K, N) = [int(p) for p in input().strip().split(' ')]
	k = K % 100
	m = K // 100
	if N == 0:
		ans = k
	else:
		d100 = sum([power(i, N) for i in range(1, 100)])
		r = 0
		if k > 0:
			r = sum([power(i, N) for i in range(1, k + 1)])
		ans = (d100 * m + r) % 100
	if ans < 10:
		print('0' + str(ans))
	else:
		print(ans)


from functools import lru_cache

def shit(i):
	if i == 0:
		return 0
	if i == 1:
		return 50
	if i % 2 == 1:
		return 0
	elif (i - 2) % 4 == 0:
		return 50
	elif i % 4 == 0:
		return 30

@lru_cache()
def ps(k, n):
	if k == 0:
		return 0
	ret = 1
	for i in range(2, k + 1):
		partial = 1
		for _ in range(n):
			partial *= i
			partial %= 100
		ret += partial
		ret %= 100
	return ret

@lru_cache()
def solve(k, n):
	(d, m) = divmod(k, 100)
	salgado = n - (n // 20 - 1) * 20
	while salgado > 33:
		salgado -= 20
	ret = d * shit(n) + ps(m, salgado)
	ret %= 100
	return ret
t = int(input())
for _ in range(t):
	(k, n) = map(int, input().split())
	print('{:02}'.format(solve(k, n)))


def fexp(a, n):
	res = 1
	while n:
		if n % 2:
			res = res * a % MOD
		a = a * a % MOD
		n //= 2
	return res
MOD = 100
for _ in range(int(input())):
	(K, N) = map(int, input().split())
	k = K % MOD
	res = 0
	resk = 0
	for i in range(1, 101):
		res += fexp(i, N)
		res %= MOD
		if i == k:
			resk = res
	res *= K // 100
	res = (res + resk) % MOD
	if res < 10:
		print('0' + str(res))
	else:
		print(res)


from itertools import accumulate
for _ in range(int(input())):
	(k, n) = list(map(int, input().split()))
	x = list(accumulate((pow(i, n, 100) for i in range(100))))
	print('%02d' % ((k // 100 * x[-1] + x[k % 100]) % 100))


p = 100
for _ in range(int(input())):
	(k, n) = [int(x) for x in input().split()]
	(q, r) = divmod(k, p)
	a = q * sum((pow(i + 1, n, p) for i in range(p)))
	b = sum((pow(i + 1, n, p) for i in range(r)))
	res = (a + b) % p
	print(str(res).zfill(2))


def solve(k, n):
	s = sum((pow(i, n, 100) for i in range(1, 101)))
	s = k // 100 * (s % 100) % 100
	p = sum((pow(i, n, 100) for i in range(1, k % 100 + 1)))
	print(('00' + str((s + p) % 100))[-2:])
for t_itr in range(int(input())):
	kn = input().split()
	k = int(kn[0])
	n = int(kn[1])
	solve(k, n)


t = int(input())
for _ in range(t):
	(k, n) = map(int, input().split())
	k += 1
	full = sum((pow(i, n, 100) for i in range(100))) % 100
	tail = sum((pow(i, n, 100) for i in range(k % 100))) % 100
	ans = (full * (k // 100) + tail) % 100
	print('{:02d}'.format(ans))


from itertools import accumulate
for _ in range(int(input())):
	(k, n) = list(map(int, input().split()))
	x = list(accumulate((pow(i, n, 100) for i in range(100))))
	print('%02d' % ((k // 100 * x[-1] + x[k % 100]) % 100))


for _ in range(int(input())):
	(k, n) = map(int, input().split())
	n = min(n, 20 + n % 20)
	f100 = [pow(i, n, 100) for i in range(100)]
	(q, r) = divmod(k + 1, 100)
	s = q % 100 * sum(f100) + sum(f100[:r])
	print('%02d' % (s % 100))


for _ in range(int(input())):
	(K, N) = map(int, input().split())
	s = 0
	for i in range(1, 100):
		s += pow(i, N, 100)
	ans = s * (K // 100) % 100
	for i in range(1, K % 100 + 1):
		ans = (ans + pow(i, N, 100)) % 100
	print(str(ans).rjust(2, '0'))


M = 100

def somme(K, N):
	(q, r) = divmod(K, M)
	a = sum((pow(i, N, M) for i in range(1, M))) % M
	b = sum((pow(i, N, M) for i in range(1, r + 1))) % M
	res = (a * q + b) % M
	return res

def main():
	T = int(input())
	for _ in range(T):
		(K, N) = map(int, input().split())
		print('%02d' % somme(K, N))
main()


def f(k, n):
	m = 100
	(q, r) = (k // m, k % m)
	li = [0] * m
	li[0] = 1
	for i in range(1, len(li)):
		li[i] += (li[i - 1] + pow(i + 1, n, m)) % m
	return (q * li[m - 1] + (0 if r == 0 else li[r - 1])) % m
for _ in range(int(input())):
	print(str(f(*[int(i) for i in input().split()])).zfill(2))


def power(x, n):
	if n == 1:
		return x
	ret = power(x * x % 100, n // 2)
	if n % 2:
		ret = ret * x % 100
	return ret

def power_calc(k, n):
	s = 0
	for ki in range(1, 100):
		m = (1 + (k - ki) // 100) % 100
		s = (s + m * power(ki, n)) % 100
	return s

def brute(k, n):
	s = 0
	for ki in range(1, k + 1):
		s = (s + power(ki, n)) % 100
	return s
T = int(input())
for _ in range(T):
	(k, n) = map(int, input().split())
	print('{:02d}'.format(power_calc(k, n)))


for _ in range(int(input())):
	(k, n) = map(int, input().split())
	a = sum([pow(z, n, 100) for z in range(1, 101)])
	c = k // 100
	c1 = k % 100
	d = sum([pow(z, n, 100) for z in range(c1 + 1)])
	e = (a * c + d) % 100
	if e < 10:
		print('0' + str(e))
	else:
		print(e)


for x in range(int(input())):
	(k, n) = map(int, input().split())
	a = sum((pow(z, n, 100) for z in range(1, 101)))
	c = k // 100
	c1 = k % 100
	d = sum((pow(z, n, 100) for z in range(c1 + 1)))
	e = (a * c + d) % 100
	if e < 10:
		print('0' + str(e))
	else:
		print(e)


import math
import os
import random
import re
import sys

def power_(i, n):
	if n == 1:
		return i % 100
	if n == 0:
		return 1
	b = power_(i, n // 2)
	if n % 2 == 0:
		return b * b % 100
	return b * b * i % 100
for _ in range(int(input())):
	(k, n) = list(map(int, input().split()))
	l = [0]
	for i in range(1, 100):
		l.append(power_(i, n))
	a = (k // 100 * sum(l) + sum(l[:k % 100 + 1])) % 100
	if a < 10:
		print('0' + str(a))
	else:
		print(a)


t = int(input())
for _ in range(t):
	(k, n) = map(int, input().split())
	k += 1
	full = sum((pow(i, n, 100) for i in range(100))) % 100
	tail = sum((pow(i, n, 100) for i in range(k % 100))) % 100
	ans = (full * (k // 100) + tail) % 100
	print('{:02d}'.format(ans))