The coordinators in galaxy H3 are keen on winning the Galactic Wars, as always. They have decided to take advice from their ancestors who have relocated to galaxy H1, through a secure computer connection. However, this would be considered a violation of the Model Code of Conduct, and hence the channel needs to be completely secure, so that the Inter-Galactic Police cannot intercept their communication

H3 citizens also know the ancient magical technique of finding the first (least-significant) digit of a^b for any integers a and b as quickly as snap. Pande and Pande have recently collaborated, for the first time ever, and produced a brilliant encryption verification algorithm using this fact. The coordinators would pick two numbers a, b and transmit it. The ancestors in H1 would calculate a^b and return it. If the correct a^b was returned, it would mean that the targetted people were sitting at the other end.

As a Martian intern at the Inter-Galactic Police, you intend to become famous by cracking this connection. Can you find the ancient technique?

Input: 

First line contains a single integer T, denoting the number of Test Cases.

T lines containing space separated integers: a and b, denoting the test case you have to crack.

Warning: Fast IO may be needed in some languages.

Output:

Output T lines each containing the least significant digit of a^b, needed to break the encryption system.

Note: 0^0 = 1

Constraints:

1 <= T <= 1000000

1 <= a <= 10^18

0<= b <= 10^18

Time Limit: 1 second

Example:

Input:

1

2 3

Output:

8

Explanation: 2^3 = 8.