Rohit was doing the work of his math class about three days but he is tired of make operations a lot and he should deliver his task tomorrow. His math’s teacher gives two numbers a and b. The problem consist in find the last digit of the potency of base a and index b. Help Rohit with his problem. You are given two integer numbers: the base a (number of digits d, such that 1 ≤ d ≤ 1000) and the index b (0 ≤ b ≤ 922*10^15). You
have to find the last digit of a^b.

Input

The first line of input contains an integer t, the number of test cases (t ≤ 30). t test cases follow. For each test case will appear a and b separated by space.

Output

For each test case output an integer per line representing the result.

SAMPLE INPUT
3
3 10
6 2
150 53

SAMPLE OUTPUT
9
6
0
for _ in range(int(input())):
	arr = list(raw_input().strip().split(' '))
	a, b = arr[0], int(arr[1])
	assert (len(a)>=1 and len(a)<=1000)
	assert (b>=0 and b<=922*(10**15))
	d = int(a[len(a) - 1])
	#print d, b
	if d == 0:
		print 0
	if d == 1:
		print 1
	if d == 2:
		if b%4 == 0:
			print 6
		elif b%4 == 1:
			print 2
		elif b%4 == 2:
			print 4
		elif b%4 == 3:
			print 8
	if d == 3:
		if b % 4 == 0:
			print 1
		elif b%4 == 1:
			print 3
		elif b%4 == 2:
			print 9
		elif b%4 == 3:
			print 7
	if d == 4:
		if b % 2 == 0:
			print 6
		else:
			print 4
	if d == 5:
		print 5
	if d == 6:
		print 6
	if d == 7:
		if b % 4 == 0:
			print 1
		elif b%4 == 1:
			print 7
		elif b%4 == 2:
			print 9
		elif b%4 == 3:
			print 3
	if d == 8:
		if b % 4 == 0:
			print 6
		elif b%4 == 1:
			print 8
		elif b%4 == 2:
			print 4
		elif b%4 == 3:
			print 2
	if d == 9:
		if b % 2 == 0:
			print 1
		else:
			print 9