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
t = int(raw_input())
for i in range(1,t+1):
 a, b = [int(x) for x in raw_input().split()]
 x=a%10
 if x==0 or x==1 or x==5 or x==6 :
  print x
 elif x==4 :
  y = b%2 
  if y==0:
   print 6
  else:
   print 4
 elif x==9 :
  y = b%2
  if y==0:
   print 1
  else:
   print 9
 else :
  y = b%4
  if x==2: 
   if y==1:
    print 2
   elif y==2:
	print 4
   elif y==3:
	print 8
   else:
	print 6
  elif x==3: 
   if y==1:
    print 3
   elif y==2:
	print 9
   elif y==3:
	print 7
   else:
	print 1
  elif x==7: 
   if y==1:
    print 7
   elif y==2:
    print 9
   elif y==3:
	print 3
   else:
	print 1
  else: 
   if y==1:
	print 8
   elif y==2:
	print 4
   elif y==3:
	print 2
   else:
	print 6
print "\n"