```go
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n int
	fmt.Fscan(reader, &n)
	var s string
	fmt.Fscan(reader, &s)

	// Precompute: for each character c and each (i,j) pair, cost[c][i][j] = number of non-c characters in s[i..j]
	// Then best[c][m] = maximum window length where cost <= m
	// We precompute best[26][n+1]

	best := [26][1501]int{}

	for c := 0; c < 26; c++ {
		ch := byte('a' + c)
		// sliding window or precompute prefix sums
		// prefix[i] = number of non-ch characters in s[0..i-1]
		prefix := make([]int, n+1)
		for i := 0; i < n; i++ {
			prefix[i+1] = prefix[i]
			if s[i] != ch {
				prefix[i+1]++
			}
		}
		// For each m from 0 to n, find max length window with at most m non-ch chars
		// Use two pointers
		// best[c][m] = max window length with cost <= m
		// First compute for all possible windows
		// best[c][m] for m=0..n
		// Initialize
		for m := 0; m <= n; m++ {
			best[c][m] = 0
		}
		// Two pointer for each m would be O(n) per m -> O(26*n^2) total which might be too slow for n=1500
		// Better: precompute maxLen[cost] = max window length with exactly 'cost' non-ch chars
		// Then best[c][m] = max(maxLen[0..m])
		
		// Actually let's compute for each window its cost and update
		// Use sliding window: for each right, find leftmost left such that cost <= m
		// But we need all m values
		
		// Alternative: for each pair (l, r), cost = prefix[r+1] - prefix[l]
		// We want max (r-l+1) = max (r+1-l) for each cost value
		// maxByExactCost[k] = max window length with exactly k non-ch chars
		maxByExactCost := make([]int, n+1)
		
		left := 0
		for right := 0; right < n; right++ {
			// cost of window [left, right] = prefix[right+1] - prefix[left]
			// We want to track for each possible cost (0..n) the max length
			// Actually easier: use sliding window to find for each right the min left for cost <= m
			// But let's just compute all windows
			_ = left
		}
		_ = left
		
		// Reset and do O(n^2) precomputation
		for i := 0; i < n; i++ {
			cost := 0
			for j := i; j < n; j++ {
				if s[j] != ch {
					cost++
				}
				length := j - i + 1
				if maxByExactCost[cost] < length {
					maxByExactCost[cost] = length
				}
			}
		}
		
		// Now best[c][m] = max over k=0..m of maxByExactCost[k]
		best[c][0] = maxByExactCost[0]
		for m := 1; m <= n; m++ {
			best[c][m] = best[c][m-1]
			if maxByExactCost[m] > best[c][m] {
				best[c][m] = maxByExactCost[m]
			}
		}
		
		// Reset maxByExactCost for next character
		for i := range maxByExactCost {
			maxByExactCost[i] = 0
		}
	}

	var q int
	fmt.Fscan(reader, &q)
	for ; q > 0; q-- {
		var m int
		var cs string
		fmt.Fscan(reader, &m, &cs)
		c := int(cs[0] - 'a')
		fmt.Fprintln(writer, best[c][m])
	}
}
```