#include <bits/stdc++.h>
using namespace std;
const int p[] = {1224469897, 1503325967, 1336143462, 937397015};
long long a[10001];
int n, m, d[20], len;
vector<int> f[17][5], pri;
int gt(int b) {
  int r = 0;
  for (int i = 0; i < (len); ++i) r = r * b + d[i];
  return r;
}
int dfs(int b, int c, int num) {
  if (~f[b][c][num]) return f[b][c][num];
  int &ret = f[b][c][num] = 1;
  for (int i = 0; i < (len); ++i)
    if (d[i] == b) {
      for (int j = 0; j < (b); ++j)
        d[i] = j, ret = (long long)ret * dfs(b, c, gt(b + 1)) % p[c];
      d[i] = b;
      return ret;
    }
  int id = gt(b);
  ret = id < n ? a[id] % p[c] : 1;
  return ret;
}
int main() {
  for (int i = 2; i < (100); ++i) {
    bool ok = true;
    for (int j = 2; j < (i); ++j) ok &= i % j != 0;
    if (ok) pri.push_back(i);
  }
  scanf("%d", &n);
  for (int b = 2; b < (17); ++b) {
    int i, j;
    for (i = j = 1; i <= n; i *= b, j *= b + 1)
      ;
    for (int k = 0; k < (4); ++k) f[b][k].resize(j, -1);
  }
  for (int i = 0; i < (n); ++i) scanf("%I64d", a + i);
  scanf("%d", &m);
  for (int re = 0; re < (m); ++re) {
    char s[40];
    int b;
    long long c;
    scanf("%d%s%I64d", &b, s, &c);
    int len = strlen(s);
    int i, j;
    for (i = 1, j = 0; i <= n; i *= b, j++)
      ;
    ::len = j;
    for (int i = 0; i < (j); ++i) {
      int k = len - j + i;
      d[i] =
          k >= 0
              ? (s[k] == '?' ? b : (s[k] <= '9' ? s[k] - '0' : s[k] - 'A' + 10))
              : 0;
    }
    int ans = 25;
    for (int i = 0; i < (4); ++i) {
      int t = (c + dfs(b, i, gt(b + 1))) % p[i];
      for (int j = 0; j < (25); ++j)
        if (t % pri[j] == 0 && p[i] % pri[j] == 0) ans = min(ans, j);
    }
    ans = ans == 25 ? -1 : pri[ans];
    printf("%d\n", ans);
  }
  return 0;
}
