#include <bits/stdc++.h>
using namespace std;
const int maxn = 80010, maxl = 100;
const int prime[26] = {0,  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};
int n, m;
long long A[maxn], c[maxn];
int D[maxn], ans[maxn];
char s[maxn][maxl];
int num[maxl];
long long F[maxn * 100];
int mul(int a, int b) {
  int c = 1;
  while (b) {
    if (b & 1) c = c * a;
    b >>= 1;
    a = a * a;
  }
  return c;
}
int main() {
  int i, j, k, l, x, y, z, d, len, tot;
  long long mo;
  scanf("%d", &n);
  for (i = 0; i < n; ++i) scanf("%I64d", &A[i]);
  scanf("%d\n", &m);
  for (i = 1; i <= m; ++i) scanf("%d %s %I64d\n", &D[i], s[i], &c[i]);
  for (i = 1; i <= 25;) {
    for (mo = 1, j = i; i <= 25 && mo <= 1000000; ++i) mo *= prime[i];
    for (d = 2; d <= 16; ++d) {
      len = 0;
      for (k = n; k; k /= d) ++len;
      tot = mul(d + 1, len);
      for (k = 0; k < tot; ++k) {
        F[k] = 1;
        if (k)
          for (x = k, num[0] = 0; x; x /= d + 1) num[++num[0]] = x % (d + 1);
        else
          num[0] = 1, num[1] = 0;
        for (x = num[0]; x >= 1 && num[x] != d; --x)
          ;
        if (x) {
          y = mul(d + 1, x - 1);
          for (z = 1; z <= d; ++z) F[k] = F[k] * F[k - z * y] % mo;
        } else {
          for (x = num[0], y = 0; x >= 1; --x) y = y * d + num[x];
          if (y < n) F[k] *= A[y] % mo;
        }
      }
      for (k = 1; k <= m; ++k)
        if (D[k] == d && !ans[k]) {
          l = strlen(s[k]);
          for (z = 0; l - z > len; ++z)
            if (s[k][z] != '?' && s[k][z] != '0') break;
          if (l - z > len) continue;
          for (x = z, y = 0; x < l; ++x)
            y = y * (d + 1) + ((s[k][x] >= 'A' && s[k][x] <= 'Z')
                                   ? s[k][x] - 'A' + 10
                               : (s[k][x] == '?') ? d
                                                  : s[k][x] - '0');
          for (x = j; x < i; ++x)
            if ((F[y] + c[k] % mo) % prime[x] == 0) {
              ans[k] = prime[x];
              break;
            }
        }
    }
  }
  for (i = 1; i <= m; ++i)
    if (ans[i])
      printf("%d\n", ans[i]);
    else
      printf("-1\n");
  return 0;
}
