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")
}

function countSubstrings(s, queries) {
    // Write your code here
    let left;
    let right;
    queries.forEach((query, index) => {
        let mainSubString = [];
        left = query[0];
        right = query[1];
        const subString = s.slice(left, right+1);
        const sstrLength = subString.length;
        for(let i=0; i<sstrLength; i++){
        for (let j = i + 1; j <= sstrLength; j++) {
            if(!mainSubString.includes(
                subString.slice(i, j))){
            mainSubString.push(subString.slice(i, j))
            }

        }
        }
        console.log(mainSubString.length)  
    })

}