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
def zerao(index):
    print 0

def one(index):
    print 1

def two(index):
    last_digits = [2, 4, 8, 6]
    print last_digits[(index % 4) - 1]

def three(index):
    last_digits = [3, 9, 7, 1]
    print last_digits[(index % 4) - 1]

def four(index):
    last_digits = [4, 6]
    print last_digits[(index % 2) - 1]

def five(index):
    print 5

def six(index):
    print 6

def seven(index):
    last_digits = [7, 9, 3, 1]
    print last_digits[(index % 4) - 1]

def eight(index):
    last_digits = [8, 4, 2, 6]
    print last_digits[(index % 4) - 1]

def nine(index):
    last_digits = [9, 1]
    print last_digits[(index % 2) - 1]

options = {
0:zerao,
1:one,
2:two,
3:three,
4:four,
5:five,
6:six,
7:seven,
8:eight,
9:nine,
};

def last_digit_potency(a, b):
    i = a % 10
    options[i](b)

def main():
    total = raw_input()
    for i in range(int(total)) :
        a,b = map(int, raw_input().split())
        if b == 0:
            print 1
        else:
            last_digit_potency(a, b)

main()