#include "bits/stdc++.h"

using namespace std;

string inmultirea(string s1, string s2)
{

    vector<int> v3(s1.size() + s2.size());

    reverse(s1.begin(), s1.end());
    reverse(s2.begin(), s2.end());

    for(int i = 0; i < s1.size(); i++) {
        for(int j = 0; j < s2.size(); j++) {
            int a = s1[i] - '0';
            int b = s2[j] - '0';
            v3[i+j] += a * b;
        }
    }

    for (int i = 0; i < v3.size()-1; i++) {
        int m = v3[i] / 10;
        v3[i+1] += m;
        v3[i] = v3[i] % 10;
    }
    if (v3[v3.size()-1] == 0) {
        v3.pop_back();
    }

    string s="";
    for (int i= 0; i < v3.size(); i++) {
        char c = v3[i] + '0';
        s = c + s;
    }
    return s;
}

string adunare( string s1, string s2)
{
    while(s1.size() < s2.size()) {
        s1="0" + s1;
    }
    while(s2.size() < s1.size()) {
        s2="0" + s2;
    }

    int m = 0, r;
    string s;
    for ( int i = s1.size() - 1; i > 0 ; i--) {
        int c1 = s1[i] - '0';
        int c2 = s2[i] - '0';
        r = (c1 + c2 + m) % 10;
        m = (c1 + c2 + m) / 10;
        s = to_string(r) + s;
    }
    int c1 = s1[0] - '0';
    int c2 = s2[0] - '0';
    r = c1 + c2 + m;
    s = to_string(r) + s;
    return s;
}

bool comparare(string s1, string s2)
{
    string s = s1;
    while(s.size() < s2.size()) {
        s="0" + s;
    }
    return s <= s2;
}

string putere (string c, string c1)
{
    string rs = "1";
    string d = "1";
    while(comparare(d,c1)) {
        rs = inmultirea(rs,c);
        d = adunare (d,"1");
    }
    return rs;
}

int main()
{
    ifstream cin("cifra.in");
    ofstream cout("cifra.out");

    int t;
    cin >> t;
    vector<string> v(t);
    for(int i = 0; i < t; i++) {
        cin >> v[i];
    }

    for (int i = 0; i < t; i++) {
        string a = "0";
        string n = "1";
        string c = adunare (v[i],"1");
        while(comparare(n,v[i])) {
            string p = putere(n,n);
            a = adunare(a,p);
            n = adunare (n,"1");
        }
        cout << a[a.size()-1] << '\n';
    }

    return 0;
}