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

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<=N<=1,000,000,000).

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

2
3
4

7
6

//Right most Digital
//拿到此题第一感觉可以通过两个数相乘然后求得最后一位，但是发现其实结果只和最后一位
//有关，用整个数来求得最后一位未免太过麻烦，便考虑去寻找规律
//便是 0所有相乘都为0,1所有相乘都为1，2相乘便是48624862...然后每一个都是循环关系，
//循环周期分别为1,1,4,4,2,1,1,4,4,2
//然后问题便转化为求末位，找规律，得结果 
#include<iostream>
#include<string>
using namespace std;
#define MAX 10000
long int n,m;
int main()
{
	int t,u;
    int a3[4]={1,3,9,7},a4[2]={6,4};
    int a2[4]={6,2,4,8},a7[4]={1,7,9,3};
    int a8[4]={6,8,4,2},a9[2]={1,9}; 
	int x[10]={1,1,4,4,2,1,1,4,4,2};//0-9分别循环次数为此数组对应数位 
	while(cin>>t)
	{
		while(t--)
		{
			cin>>n;//幂次，n的n次方
			while(n!=0)
			{
				m=n%10;
				n=n/10;
			} 
			//除10取余，获取最后一位数字
			u=m; 
			u=u%x[m];//u即为所除余数 
			if(m==0||m==1||m==5||m==6)
			{
				cout<<m<<endl;
			} 
			else if(m==2)      cout<<a2[u]<<endl;
			else if(m==3)      cout<<a3[u]<<endl;
			else if(m==4)      cout<<a4[u]<<endl;
			else if(m==7)      cout<<a7[u]<<endl;
			else if(m==8)      cout<<a8[u]<<endl;
			else if(m==9)      cout<<a9[u]<<endl;
		}
	}
}