#include <bits/stdc++.h>
using namespace std;
void Get(int &T) {
  char C;
  bool F = 0;
  for (; C = getchar(), C < '0' || C > '9';)
    if (C == '-') F = 1;
  for (T = C - '0'; C = getchar(), C >= '0' && C <= '9'; T = T * 10 + C - '0')
    ;
  F && (T = -T);
}
void Get(long long &T) {
  char C;
  bool F = 0;
  for (; C = getchar(), C < '0' || C > '9';)
    if (C == '-') F = 1;
  for (T = C - '0'; C = getchar(), C >= '0' && C <= '9'; T = T * 10 + C - '0')
    ;
  F && (T = -T);
}
int N, M;
long long A[10005];
const long long Mod[] = {0, 223092870, 58642669, 600662303, 33984931, 8633};
void Init() {
  Get(N);
  for (int i = 0; i < N; i++) Get(A[i]);
}
vector<long long> F[15][25];
char S[35];
long long Ans[15];
int Prime[] = {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 L[25];
long long DP(int Type, int D, int Depth, int Val, int Pow = 1) {
  if (F[Type][D][Val] != -1) return F[Type][D][Val];
  if (Depth > L[D]) {
    int ID = 0;
    for (int i = L[D]; i >= 1; i--) ID = ID * D + S[i];
    F[Type][D][Val] = 1;
    if (ID < N) F[Type][D][Val] = A[ID] % Mod[Type];
    return F[Type][D][Val];
  }
  if (S[Depth] == D) {
    long long Ans = 1;
    for (int k = 0; k < D; k++) {
      S[Depth] = k;
      (Ans *= DP(Type, D, Depth + 1, Val - (D - k) * Pow, Pow * (D + 1))) %=
          Mod[Type];
      S[Depth] = D;
    }
    F[Type][D][Val] = Ans;
  } else {
    F[Type][D][Val] = DP(Type, D, Depth + 1, Val, Pow * (D + 1));
  }
  return F[Type][D][Val];
}
int Calc() {
  for (int i = 1; i <= 25; i++) {
    for (int j = 1; j <= 5; j++) {
      if (Mod[j] % Prime[i] == 0) {
        if (Ans[j] % Prime[i] == 0) return Prime[i];
      }
    }
  }
  return -1;
}
void Work() {
  for (int i = 2; i <= 16; i++) {
    int Cnt = 0, Len = 1;
    for (int k = N - 1; k > 0; k /= i) {
      Cnt++;
      Len *= (i + 1);
    }
    L[i] = Cnt;
    for (int j = 1; j <= 5; j++) F[j][i].resize(Len, -1);
  }
  int D;
  long long C;
  int Len;
  Get(M);
  for (int k = 1; k <= M; k++) {
    Get(D);
    scanf("%s", S + 1);
    Get(C);
    Len = strlen(S + 1);
    for (int i = 1, j = Len; i < j; i++, j--) std::swap(S[i], S[j]);
    int Large = 0;
    for (int i = L[D] + 1; i <= Len; i++) {
      if (S[i] == '?') S[i] = '0';
      if (S[i] != '0') {
        Large = 1;
        for (int j = 1; j <= 5; j++) Ans[j] = (1 + C) % Mod[j];
        break;
      }
    }
    for (int i = 1; i <= Len; i++) {
      switch (S[i]) {
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':
          S[i] = S[i] - '0';
          break;
        case 'A':
        case 'B':
        case 'C':
        case 'D':
        case 'E':
        case 'F':
          S[i] = S[i] - 'A' + 10;
          break;
        case '?':
          S[i] = D;
          break;
      }
    }
    if (Large == 0) {
      long long Val = 0;
      for (int i = Len; i >= 1; i--) {
        Val = Val * (D + 1) + S[i];
      }
      for (int i = 1; i <= 5; i++) {
        Ans[i] = (DP(i, D, 1, Val) + C) % Mod[i];
      }
    }
    int Ans = Calc();
    printf("%d\n", Ans);
  }
}
int main() {
  Init();
  Work();
}
