import java.io.*;
import java.util.*;

/**
 * TLE submission for ASQP. This solution uses the kmp algorithm for each
 * substring pattern. This has worst case complexity O(nk) in the case 
 * where all pattern substrings have length 1.
 *
 * @author Finn Lidbetter
 */

public class asqp_kmp {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();

    String text = br.readLine();
    int k = Integer.parseInt(br.readLine());
    for (int i=0; i<k; i++) {
      String[] pair = br.readLine().split(" ");
      String pattern = pair[0];
      int order = Integer.parseInt(pair[1]);
      int index = kmp(text, pattern, order);
      sb.append(index+"\n");
    }
    System.out.print(sb);
  }
  static int kmp(String txt, String pat, int order) {
    int m = pat.length();
    int n = txt.length();
    int i = 0;
    int j = 0; 
    int count = 0;
    int[] arr = kmpHelper(pat, m);
    while (i < n) {
      if (pat.charAt(j)==txt.charAt(i)) { 
        j++; 
        i++; 
      }
      if (j==m) {
        count++; // match at i-j
        if (count==order) {
          return i-j + 1;
        }
        j = arr[j-1];
      } else if (i<n && pat.charAt(j)!=txt.charAt(i)) {
        if (j!=0) 
          j = arr[j-1];
        else i = i+1; 
      } 
    }
    return -1;
  }
  static int[] kmpHelper(String pat, int m) {
    int [] arr = new int[m];
    for (int i=1, len=0; i<m;) {
      if (pat.charAt(i) == pat.charAt(len)) {
        arr[i++] = ++len;
      } else {
        if (len>0) 
          len = arr[len-1];
        else 
          i++;
      }
    }
    return arr;
  }
}
