Given two numbers a and b. Find the last digit of a^b. (a to the power b).

Input

There will be t (1 <= t <= 10) test cases. In each case there will be two number a (1 <= a <= 10^100000) and b (1 <= b <= 10^100000) separated by a space.

Output

Print the last digit of a^b in a single line.

Example

Input:
2
3 10
6 2

Output:
9
6