def compute_z(s):
    n = len(s)
    Z = [0] * n
    Z[0] = n
    l, r = 0, 0
    for i in range(1, n):
        if i > r:
            l = r = i
            while r < n and s[r - l] == s[r]:
                r += 1
            Z[i] = r - l
            r -= 1
        else:
            k = i - l
            if Z[k] < r - i + 1:
                Z[i] = Z[k]
            else:
                l = i
                while r < n and s[r - l] == s[r]:
                    r += 1
                Z[i] = r - l
                r -= 1
    return Z

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    Q = int(input[ptr])
    ptr += 1
    S = input[ptr]
    ptr += 1
    queries = []
    for _ in range(Q):
        L = int(input[ptr]) - 1  # converting to 0-based
        ptr += 1
        R = int(input[ptr]) - 1
        ptr += 1
        queries.append((L, R))
    
    for L, R in queries:
        M = R - L + 1
        T = S[L:L+M]
        T_prime = T + '#' + S
        Z = compute_z(T_prime)
        ans = 0
        for i in range(N):
            pos = M + 1 + i
            if pos >= len(Z):
                l_i = 0
            else:
                l_i = min(Z[pos], M)
            count_B = min(l_i, M-1)
            count_A = 0
            if l_i < M:
                if i + l_i >= N:
                    pass
                else:
                    if L + l_i > R:
                        pass
                    else:
                        if S[i + l_i] < S[L + l_i]:
                            count_A = N - (i + l_i)
            ans += count_B + count_A
        print(ans)

if __name__ == "__main__":
    main()