Migrated from Lutece 1009 Rightmost Digit

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Given a positive integer $N$, you should output the most right digit of $N^N$.

Input

The input contains several test cases. The first line of the input is a single integer $T$ which is the number of test cases. $T$ test cases follow.

Each test case contains a single positive integer $N(1 \leq N \leq 1,000,000,000)$.

Output

For each test case, you should output the rightmost digit of $N^N$.

Samples

2
3
4

7
6

Note

In the first case, $3 \times 3 \times 3 = 27$, so the rightmost digit is $7$.

In the second case, $4 \times 4 \times 4 \times 4 = 256$, so the rightmost digit is $6$.

Resources

HDU