#include <bits/stdc++.h>
using namespace std;
inline void read(int &x) {
  int v = 0, f = 1;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-')
    f = -1;
  else
    v = v * 10 + c - '0';
  while (isdigit(c = getchar())) v = v * 10 + c - '0';
  x = v * f;
}
inline void read(long long &x) {
  long long v = 0ll, f = 1ll;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-')
    f = -1;
  else
    v = v * 10 + c - '0';
  while (isdigit(c = getchar())) v = v * 10 + c - '0';
  x = v * f;
}
inline void readc(char &x) {
  char c;
  while ((c = getchar()) == ' ')
    ;
  x = c;
}
inline void writes(string s) { puts(s.c_str()); }
inline void writeln() { writes(""); }
inline void writei(int x) {
  if (x < 0) {
    putchar('-');
    x = abs(x);
  }
  if (!x) putchar('0');
  char a[25];
  int top = 0;
  while (x) {
    a[++top] = (x % 10) + '0';
    x /= 10;
  }
  while (top) {
    putchar(a[top]);
    top--;
  }
}
inline void writell(long long x) {
  if (x < 0) {
    putchar('-');
    x = abs(x);
  }
  if (!x) putchar('0');
  char a[25];
  int top = 0;
  while (x) {
    a[++top] = (x % 10) + '0';
    x /= 10;
  }
  while (top) {
    putchar(a[top]);
    top--;
  }
}
const long long mod[4] = {1224469897, 1503325967, 1336143462, 937397015},
                p[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};
long long n, m, i, j, a[10005], l[18], c, d, t, x, y, len;
vector<long long> f[19][4];
char ss[35];
int toi(char c) {
  if (isdigit(c)) return c & 15;
  return (c & 15) + 9;
}
long long dfs(long long d, long long p, long long x) {
  if (f[d][p][x] != -1) return f[d][p][x];
  f[d][p][x] = 1;
  int i, j;
  long long t = x, pw = 1, pw0 = 1, g = 0;
  for (((i)) = (1); ((i)) <= ((len)); ((i))++) {
    if (t % (d + 1) == d) {
      long long y = x - pw * d;
      for ((j) = (0); (j) <= (d - 1); (j)++) {
        (f[d][p][x] *= dfs(d, p, y)) %= mod[p];
        y += pw;
      }
      return f[d][p][x];
    }
    g = g + t % (d + 1) * pw0;
    t /= (d + 1);
    pw *= d + 1;
    pw0 *= d;
  }
  if (g < n) {
    return f[d][p][x] = a[g] % mod[p];
  }
  return f[d][p][x];
}
int main() {
  read(n);
  for ((i) = (0); (i) <= (n - 1); (i)++) read(a[i]);
  for ((i) = (2); (i) <= (16); (i)++) {
    x = y = 1;
    while (x < n) {
      x *= i;
      y *= i + 1;
      l[i]++;
    }
    for ((j) = (0); (j) <= (3); (j)++) f[i][j].resize(y, -1);
  }
  read(m);
  while (m--) {
    read(d);
    scanf(" %s", ss + 1);
    read(c);
    x = 0;
    int tlen = strlen(ss + 1);
    for (i = 1; i <= tlen && i <= l[d]; len = (i++))
      x = x * (d + 1) +
          (ss[tlen - l[d] + i] == '?' ? d : toi(ss[tlen - l[d] + i]));
    long long ans = 25;
    for ((i) = (0); (i) <= (3); (i)++) {
      long long t = (c + dfs(d, i, x)) % mod[i];
      for ((j) = (0); (j) <= (24); (j)++)
        if (mod[i] % p[j] == 0 && t % p[j] == 0) ans = min(ans, j);
    }
    printf("%I64d\n", p[ans]);
  }
  return 0;
}
