#include <bits/stdc++.h>
using namespace std;
struct pyt {
  string wzo;
  long long c;
  int nr, stan;
};
vector<long long> pier;
int cyf(char x) {
  if (x >= '0' && x <= '9') return x - '0';
  return 10 + (x - 'A');
}
int Pot(int p, int w) {
  int o = 1;
  for (int i = 0; i < w; ++i) o *= p;
  return o;
}
int main() {
  ios_base::sync_with_stdio(0);
  int n;
  cin >> n;
  vector<long long> a(n);
  for (int i = 0; i < n; ++i) cin >> a[i];
  int m;
  cin >> m;
  vector<vector<pyt> > b(17);
  for (int i = 0; i < m; ++i) {
    int pod;
    string wzoT;
    long long c;
    cin >> pod >> wzoT >> c;
    b[pod].push_back({wzoT, c, i, 0});
  }
  vector<int> odp(m, 100);
  vector<int> pier;
  pier.push_back(2);
  for (int i = 3; i < 100; ++i) {
    bool jest = false;
    for (int j = 2; j < i; ++j)
      if (i % j == 0) jest = true;
    if (!jest) pier.push_back(i);
  }
  for (int i = 2; i <= 16; ++i) {
    int dl = 0, x = n;
    while (x != 0) {
      ++dl;
      x /= i;
    }
    for (int j = 0; j < b[i].size(); ++j) {
      if (b[i][j].wzo.size() > dl) {
        int r = b[i][j].wzo.size() - dl;
        for (int k = 0; k < r; ++k)
          if (b[i][j].wzo[k] != '?' && b[i][j].wzo[k] != '0')
            odp[b[i][j].nr] = -1;
        b[i][j].wzo.erase(0, r);
      }
      if (b[i][j].wzo.size() < dl) {
        int r = dl - b[i][j].wzo.size();
        b[i][j].wzo = string(r, '0') + b[i][j].wzo;
      }
      for (int k = 0; k < b[i][j].wzo.size(); ++k)
        b[i][j].stan = b[i][j].stan * (i + 1) +
                       ((b[i][j].wzo[k] == '?') ? i : cyf(b[i][j].wzo[k]));
    }
    int ilWzo = Pot(i + 1, dl);
    for (int l = 0; l < pier.size();) {
      int p = l, MOD = 1;
      while (p < pier.size() && MOD * pier[p] <= 10000000) {
        MOD *= pier[p];
        ++p;
      }
      --p;
      vector<int> dp(ilWzo, -1);
      for (int j = 0; j < ilWzo; ++j) {
        x = j;
        int znZap = 0;
        while (x != 0) {
          if (x % (i + 1) == i) break;
          ++znZap;
          x /= i + 1;
        }
        int pop;
        if (x == 0) {
          int pot = 1;
          pop = 0;
          x = j;
          while (x != 0) {
            pop = pop + (x % (i + 1)) * pot;
            x /= i + 1;
            pot *= i;
          }
          if (pop < n) dp[j] = a[pop] % MOD;
        } else {
          bool jestJakis = false;
          dp[j] = 1;
          for (int k = 0; k < i; ++k) {
            pop = j + (k - i) * Pot(i + 1, znZap);
            if (dp[pop] != -1) {
              dp[j] = ((long long)dp[j] * dp[pop]) % MOD;
              jestJakis = true;
            }
          }
          if (!jestJakis) dp[j] = -1;
        }
      }
      for (int j = 0; j < b[i].size(); ++j) {
        for (int k = l; k <= p; ++k) {
          int ilo = dp[b[i][j].stan];
          if (ilo == -1) ilo = 1;
          if ((ilo + b[i][j].c % MOD) % pier[k] == 0)
            odp[b[i][j].nr] = min(odp[b[i][j].nr], pier[k]);
        }
      }
      l = p + 1;
    }
  }
  for (int i = 0; i < m; ++i) {
    if (odp[i] == 100)
      cout << "-1" << endl;
    else
      cout << odp[i] << endl;
  }
  return 0;
}
