#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
ll fib(ll f[], ll n)
{
f[0] = 0;
f[1] = 1;
for (ll i = 2; i <= n; i++)
f[i] = (f[i - 1] + f[i - 2]) % 10;
return f[n];
}
ll findLastDigit(ll n)
{
ll f[60];
fib(f, 60);
return f[n % 60];
}
ll countbase(ll n)
{
ll c=0;
while(n!=0)
{
n/=2;
c++;
}
return c-1;
}
int main()
{
ll t; cin>>t; while(t--)
{
ll n; cin>>n;
//ll x=(log2(n));
ll y=countbase(n);
//cout<<x<<" "<<y<<endl;
ll index=pow(2,y)-1;
//cout<<index<<endl;
cout<<findLastDigit(index)<<endl;
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgdW5zaWduZWQgbG9uZyBsb25nIGxsOwoKbGwgZmliKGxsIGZbXSwgbGwgbikKewoJZlswXSA9IDA7CglmWzFdID0gMTsKCgoJZm9yIChsbCBpID0gMjsgaSA8PSBuOyBpKyspCgkJZltpXSA9IChmW2kgLSAxXSArIGZbaSAtIDJdKSAlIDEwOwoKCXJldHVybiBmW25dOwp9CgpsbCBmaW5kTGFzdERpZ2l0KGxsIG4pCnsKCWxsIGZbNjBdOwoJZmliKGYsIDYwKTsKCglyZXR1cm4gZltuICUgNjBdOwp9CgpsbCBjb3VudGJhc2UobGwgbikKewogICAgbGwgYz0wOwogICAgd2hpbGUobiE9MCkKICAgIHsKICAgICAgICBuLz0yOwogICAgICAgIGMrKzsKICAgIH0KICAgIHJldHVybiBjLTE7Cgp9CgppbnQgbWFpbigpCnsKCiAgICBsbCB0OyBjaW4+PnQ7IHdoaWxlKHQtLSkKICAgIHsKICAgICAgICBsbCBuOyBjaW4+Pm47CiAgICAgICAgLy9sbCB4PShsb2cyKG4pKTsKICAgICAgICBsbCB5PWNvdW50YmFzZShuKTsKICAgICAgICAvL2NvdXQ8PHg8PCIgIjw8eTw8ZW5kbDsKICAgICAgICBsbCBpbmRleD1wb3coMix5KS0xOwogICAgICAgIC8vY291dDw8aW5kZXg8PGVuZGw7CiAgICAgICAgY291dDw8ZmluZExhc3REaWdpdChpbmRleCk8PGVuZGw7CiAgICB9CgogICAgcmV0dXJuIDA7Cn0KCgo=