#include <bits/stdc++.h>
using namespace std;
const int maxn = 10010, mo[] = {1224469897, 1503325967, 1336143462, 937397015};
const long long MAX = 5000000;
const int prime[][7] = {{7, 17, 37, 47, 61, 97},
                        {11, 13, 41, 43, 67, 89},
                        {2, 3, 23, 31, 53, 71, 83},
                        {5, 19, 29, 59, 73, 79}};
int n, m, k;
long long a[maxn], f[MAX][4], e[20], ee[20];
struct query {
  int d, ans, no;
  string p;
  long long c;
} tmp;
vector<query> Q[20], R;
inline bool cmp(const query &a, const query &b) { return a.no < b.no; }
void work(int d) {
  if (Q[d].size() == 0) return;
  int digit = 0, tmp = n;
  while (tmp) digit++, tmp /= d;
  for (int v = k = 1; v <= digit; k++, v++) e[k] = e[k - 1] * (d + 1);
  k = digit;
  for (int i = 0; i < e[k]; i++) {
    bool flag = true;
    for (int p = 0; p < 4; p++) f[i][p] = 1;
    for (int j = 0; j < k; j++) {
      if (i / e[j] % (d + 1) == d) {
        flag = false;
        int s = i - d * e[j];
        for (int t = 0; t < d; t++)
          for (int p = 0; p < 4; p++) {
            int ss = s + t * e[j];
            f[i][p] = (f[i][p] * f[ss][p]) % mo[p];
          }
        break;
      }
    }
    if (flag) {
      int s = 0;
      for (int j = 0, v = 1; j < k; v *= d, j++) s += i / e[j] % (d + 1) * v;
      if (s >= n) continue;
      for (int p = 0; p < 4; p++) f[i][p] = a[s] % mo[p];
    }
  }
  for (int i = 0; i < (int)Q[d].size(); i++) {
    long long s = 0;
    Q[d][i].ans = 101;
    for (int j = 0; j < min((int)Q[d][i].p.length(), k); j++) {
      long long tmp;
      if (Q[d][i].p[j] == '?')
        tmp = d;
      else if (Q[d][i].p[j] >= '0' && Q[d][i].p[j] <= '9')
        tmp = Q[d][i].p[j] - '0';
      else
        tmp = Q[d][i].p[j] - 'A' + 10;
      s += tmp * e[j];
    }
    bool flag = false;
    for (int j = k; j < (int)Q[d][i].p.length(); j++)
      if (Q[d][i].p[j] != '?' && Q[d][i].p[j] != '0') flag = true;
    for (int p = 0; p < 4; p++) {
      int w = p == 2 ? 7 : 6;
      long long T = flag ? 0 : f[s][p];
      for (int j = 0; j < w; j++) {
        long long tmp = (T + Q[d][i].c) % prime[p][j];
        if (!tmp) Q[d][i].ans = min(Q[d][i].ans, prime[p][j]);
      }
    }
    if (Q[d][i].ans == 101) Q[d][i].ans = -1;
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  cin >> m;
  for (int i = 0; i < m; i++) {
    cin >> tmp.d >> tmp.p >> tmp.c;
    tmp.no = i;
    reverse(tmp.p.begin(), tmp.p.end());
    Q[tmp.d].push_back(tmp);
  }
  e[0] = ee[0] = 1;
  for (int i = 2; i <= 16; i++) work(i);
  for (int i = 2; i <= 16; i++)
    for (int j = 0; j < (int)Q[i].size(); j++) R.push_back(Q[i][j]);
  sort(R.begin(), R.end(), cmp);
  for (int i = 0; i < (int)R.size(); i++) cout << R[i].ans << endl;
}
