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
__author__ = 'apritam'


data_map = {}

j=1
while j<=10:
    k=1
    while k <=10:
        if data_map.has_key(j):
            l= data_map[j]
            if l.has_key(k-1):
                l[k]=(l[k-1]*j)%10
        else:
            d = {}
            d[k]=j
            data_map[j]=d
        k+=1
    j += 1

def getNumber(base,ind,mfactor):
    if(base == 0 or mfactor==0):
        return 0
    else:
        factor = ind/10
        modulus = ind%10

        modulo_result = 1
        base_result = base

        if(modulus==0 and factor==0):
            return mfactor

        if modulus>0:
            modulo_result = data_map[base][modulus]
        if factor>0:
            base_result = data_map[base_result][10]
            if factor >1:
                return getNumber(base_result,factor,(modulo_result*mfactor)%10)
    return (base_result*modulo_result*mfactor)%10

number_of_test_case=int(raw_input())
i = 0
while i< number_of_test_case:
    b_i=raw_input().split(' ')
    base = long(str(b_i[0])[-1:])
    ind = long(b_i[1])
    print getNumber(base,ind,1)
    i +=1