// Arup Guha
// 8/19/2026
// Solution to 2026 UCF Locals Problem: Multiply My Digits

using namespace std;
#include <bits/stdc++.h>

int go(vector<bool>& hasDigit, int k, int n);

int main() {

    // Process cases.
    int nC;
    cin >> nC;
    for (int loop=0; loop<nC; loop++) {

        // Read int, initialize has array.
        string s;
        cin >> s;
        int n = stoi(s);
        vector<bool> has(10,false);
        for (int i=0; i<s.size(); i++)
            has[s[i]-'0'] = true;

        // Solve and print.
        cout << go(has, 2, n) << endl;
    }

    return 0;
}

int go(vector<bool>& hasDigit, int k, int n) {

    // We got it.
    if (n == 1) return 1;

    // Finished all the digits, no can do.
    if (k == 10) return 0;

    // If it divides, try it.
    if (hasDigit[k] && n%k == 0) {
        int tmp = go(hasDigit, k, n/k);
        if (tmp) return 1;
    }

    // If the above didn't work, then skip!
    return go(hasDigit, k+1, n);
}