#include <bits/stdc++.h>
using namespace std;
int primes[25] = {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 precalc[25][100][100];
int mxlen[22];
char jmp[17][262146][25], jmp2[4800010][25], a[25];
int dig[33], cur[33], kd;
int n, q;
int main() {
  for (int i = 0; i < 25; i++) {
    for (int a = 0; a < primes[i]; a++)
      for (int b = 0; b < primes[i]; b++) {
        precalc[i][a][b] = (a * b) % primes[i];
      }
  }
  for (int R = 2; R <= 16; R++) {
    int x = 1;
    mxlen[R] = 0;
    while (x < 10000) {
      mxlen[R]++;
      x *= R;
    }
  }
  for (int i = 0; i <= 16; i++)
    for (int j = 0; j < 262146; j++)
      for (int k = 0; k < 25; k++) jmp[i][j][k] = 1;
  for (int i = 0; i < 4800010; i++)
    for (int j = 0; j < 25; j++) jmp2[i][j] = 1;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    long long val;
    scanf("%lld", &val);
    for (int i = 0; i < 25; i++) a[i] = val % primes[i];
    for (int R = 2; R <= 16; R++) {
      kd = 0;
      int tmp = i;
      while (kd < mxlen[R]) {
        kd++;
        dig[kd] = tmp % R;
        tmp /= R;
      }
      int rg = R == 2 ? 7 : kd;
      for (int msk = 0; msk < (1 << rg); msk++) {
        int id = 0;
        for (int j = kd; j >= 1; j--) {
          id = id * (R + 1);
          if (msk >> (j - 1) & 1)
            id += R;
          else
            id += dig[j];
        }
        for (int j = 0; j < 25; j++) {
          if (R == 2)
            jmp2[id][j] = precalc[j][jmp2[id][j]][a[j]];
          else
            jmp[R][id][j] = precalc[j][jmp[R][id][j]][a[j]];
        }
      }
    }
  }
  scanf("%d", &q);
  while (q--) {
    int di;
    long long ci;
    char s[33];
    scanf("%d%s%lld", &di, s, &ci);
    int len = strlen(s);
    for (int i = 1; i <= len; i++) {
      if ('0' <= s[len - i] && s[len - i] <= '9')
        dig[i] = s[len - i] - '0';
      else if (s[len - i] == '?')
        dig[i] = di;
      else
        dig[i] = s[len - i] - 'A' + 10;
    }
    while (len < mxlen[di]) {
      len++;
      dig[len] = 0;
    }
    for (int i = 0; i < 25; i++) cur[i] = 1;
    bool ok = 1;
    if (len > mxlen[di]) {
      for (int j = mxlen[di] + 1; j <= len; j++) {
        if (dig[j] != 0 && dig[j] != di) ok = 0;
      }
    }
    if (ok) {
      if (di > 2) {
        int id = 0;
        for (int i = mxlen[di]; i >= 1; i--) id = id * (di + 1) + dig[i];
        for (int i = 0; i < 25; i++) cur[i] = jmp[di][id][i];
      } else {
        for (int msk = 0; msk < (1 << 7); msk++) {
          int id = 0;
          ok = 1;
          for (int i = len; i >= 1; i--) {
            id = id * 3;
            if (i > 7) {
              if (dig[i] == 2) {
                if (msk >> (i - 8) & 1) id++;
              } else {
                if ((dig[i] == 1) ^ (msk >> (i - 8) & 1)) {
                  ok = 0;
                  break;
                }
                id += dig[i];
              }
            } else
              id += dig[i];
          }
          if (ok) {
            for (int i = 0; i < 25; i++)
              cur[i] = precalc[i][cur[i]][jmp2[id][i]];
          }
        }
      }
    }
    int ans = -1;
    for (int i = 0; i < 25; i++) {
      if ((cur[i] + ci) % primes[i] == 0) {
        ans = primes[i];
        break;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}
