#include <bits/stdc++.h>
using namespace std;
const long long Mo[5] = {223092870LL, 2756205443LL, 907383479LL, 42600829LL,
                         97LL};
const int pri[26] = {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};
int ans, i, j, t, k, l, m, n, a, b, T, d, B[40];
long long A[10010], z, js;
char s[40];
vector<long long> f[17][5];
int calc(int d, int p) {
  int x = 0;
  for (int i = t; i >= 1; i--) x = x * (d + 1) + B[i];
  if (f[d][p][x] != -1) return x;
  f[d][p][x] = 1;
  for (int i = t; i >= 1; i--) {
    if (B[i] == d) {
      for (int j = 0; j < d; j++)
        B[i] = j, (f[d][p][x] *= f[d][p][calc(d, p)]) %= Mo[p];
      B[i] = d;
      return x;
    }
  }
  int y = 0;
  for (int i = t; i >= 1; i--) y = y * d + B[i];
  if (y < n) f[d][p][x] = A[y] % Mo[p];
  return x;
}
int main() {
  scanf("%d", &n);
  for (i = 0; i < n; i++) scanf("%I64d", A + i);
  for (i = 2; i <= 16; i++) {
    for (a = 1, b = 1; a <= n; a *= i, b *= (i + 1))
      ;
    for (j = 0; j < 5; j++) f[i][j].resize(b, -1);
  }
  for (scanf("%d", &T); T; T--) {
    scanf("%d %s %I64d", &d, s + 1, &z);
    m = strlen(s + 1);
    for (t = 0, a = 1; a <= n; t++, a *= d)
      ;
    t = t > m ? m : t;
    for (i = 1; i <= t; i++)
      B[i] = s[m - i + 1] == '?'
                 ? d
                 : (s[m - i + 1] <= '9' ? s[m - i + 1] - '0'
                                        : s[m - i + 1] - 'A' + 10);
    ans = 101;
    for (i = 0; i < 5; i++) {
      k = calc(d, i);
      js = (f[d][i][k] + z) % Mo[i];
      for (j = 0; j < 26; j++)
        if (!(Mo[i] % pri[j]) && !(js % pri[j]))
          ans = ans > 100 || ans == -1
                    ? pri[j]
                    : (pri[j] == -1 ? ans : min(ans, pri[j]));
    }
    printf("%d\n", ans);
  }
  return 0;
}
