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 i in range(input()):
	a,b=raw_input().split()
	num=a[::-1][0]
	num=int(num)
	b=int(b)
	if b==0:print 1
	elif num==0:print 0
	elif num==1:print 1
	elif num==2:
		val=b%4
		if val==1:print 2
		elif val==2:print 4
		elif val==3:print 8
		elif val==0:print 6
	elif num==3:
		val=b%4
		if val==1:print 3
		elif val==2:print 9
		elif val==3:print 7
		elif val==0:print 1
	elif num==4:
		if b%2:print 4
		else :print 6
	elif num==5:print 5
	elif num==6:print 6
	elif num==7:
		val=b%4
		if val==1:print 7
		elif val==2:print 9
		elif val==3:print 3
		elif val==0:print 1
	elif num==8:
		val=b%4
		if val==1:print 8
		elif val==2:print 4
		elif val==3:print 2
		elif val==0:print 6
	elif num==9:
		if b%2:print 9
		else:print 1