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
n=input("")
dic={0:0,1:1,2:4,3:4,4:2,5:1,6:1,7:4,8:4,9:2}
for i in range(n):
	a,b=raw_input("").split(" ")
	a=int(a)
	b=int(b)
	ld=a%10;
	pc=dic[ld];
	if ld!=0:
		rem=b%pc
		if(rem!=0):
			ud=(ld**rem)%10
		else:
			ud=(ld**pc)%10
	else:
		ud=0
	print ud