input <- readLines("stdin")

# Extract n and q from the first line
first_line <- strsplit(input[1], " ")[[1]]
n <- as.integer(first_line[1])
q <- as.integer(first_line[2])

# Extract the string
s <- input[2]

# Process each query
for (i in 3:(3 + q - 1)) {
  query_line <- strsplit(input[i], " ")[[1]]
  l <- as.integer(query_line[1]) + 1  # Convert to 1-based indexing
  r <- as.integer(query_line[2]) + 1  # Convert to 1-based indexing
  
  # Extract the substring
  substring <- substr(s, l, r)
  
  # Initialize a set to store unique substrings
  unique_substrings <- new.env(hash = TRUE)
  
  # Generate all possible substrings
  len_substring <- nchar(substring)
  for (len in 1:len_substring) {
    for (start in 1:(len_substring - len + 1)) {
      current_sub <- substr(substring, start, start + len - 1)
      unique_substrings[[current_sub]] <- TRUE
    }
  }
  
  # Count distinct substrings
  distinct_count <- length(unique_substrings)
  
  # Print the result
  cat(distinct_count, "\n")
}