#include <bits/stdc++.h>
using namespace std;
const int ww[] = {2,  3,  5,  7,  11, 13, 17, 19, 23, 29, 31, 37, 41,
                  43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, -1};
const long long mo[] = {223092870ll, 2756205443ll, 907383479ll, 42600829ll,
                        97ll};
long long a[10000], c, ans;
vector<long long> f[18][5];
int b[100], n, m, t, d, i, j, k, l;
string s;
void prepare() {
  for (i = 2; i <= 16; i++) {
    for (j = 0, k = l = 1; k <= n; k *= i, l *= i + 1)
      ;
    for (j = 0; j < 5; j++) f[i][j].resize(l, -1);
  }
}
int calc(int d, int p) {
  int i, j, x = 0, y = 0;
  for (i = 0; i < t; i++) x = x * (d + 1) + b[i];
  if (f[d][p][x] != -1) return x;
  f[d][p][x] = 1;
  for (i = 0; i < t; i++)
    if (b[i] == d) {
      for (j = 0; j < d; j++) {
        b[i] = j;
        f[d][p][x] = f[d][p][x] * f[d][p][calc(d, p)] % mo[p];
      }
      b[i] = d;
      return x;
    }
  for (i = 0; i < t; i++) y = y * d + b[i];
  if (y < n) f[d][p][x] = a[y] % mo[p];
  return x;
}
int main() {
  ios::sync_with_stdio(0);
  cin >> n;
  for (i = 0; i < n; i++) cin >> a[i];
  prepare();
  cin >> m;
  while (m--) {
    cin >> d >> s >> c;
    for (t = 0, j = 1; j <= n; t++, j *= d)
      ;
    for (j = 0; j < t; j++) {
      k = s.length() - t + j;
      b[j] =
          k >= 0
              ? (s[k] == '?' ? d : (s[k] <= '9' ? s[k] - '0' : s[k] + 10 - 'A'))
              : 0;
    }
    for (i = 0; i < 5; i++) {
      j = calc(d, i);
      ans = (f[d][i][j] + c) % mo[i];
      for (j = 0; j < 25; j++)
        if ((mo[i] % ww[j] == 0) && (ans % ww[j] == 0)) break;
      if (j < 25) break;
    }
    cout << ww[j] << endl;
  }
}
