Let's call the string beautiful if it does not contain a substring of length at least $2$, which is a palindrome. Recall that a palindrome is a string that reads the same way from the first character to the last and from the last character to the first. For example, the strings a, bab, acca, bcabcbacb are palindromes, but the strings ab, abbbaa, cccb are not.

Let's define cost of a string as the minimum number of operations so that the string becomes beautiful, if in one operation it is allowed to change any character of the string to one of the first $3$ letters of the Latin alphabet (in lowercase).

You are given a string $s$ of length $n$, each character of the string is one of the first $3$ letters of the Latin alphabet (in lowercase).

You have to answer $m$ queries — calculate the cost of the substring of the string $s$ from $l_i$-th to $r_i$-th position, inclusive.


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the length of the string $s$ and the number of queries.

The second line contains the string $s$, it consists of $n$ characters, each character one of the first $3$ Latin letters.

The following $m$ lines contain two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) — parameters of the $i$-th query.


-----Output-----

For each query, print a single integer — the cost of the substring of the string $s$ from $l_i$-th to $r_i$-th position, inclusive.


-----Examples-----

Input
5 4
baacb
1 3
1 5
4 5
2 3
Output
1
2
0
1


-----Note-----

Consider the queries of the example test.

in the first query, the substring is baa, which can be changed to bac in one operation;

in the second query, the substring is baacb, which can be changed to cbacb in two operations;

in the third query, the substring is cb, which can be left unchanged;

in the fourth query, the substring is aa, which can be changed to ba in one operation.

Difficulty: MEDIUM_HARD
Tags: String algorithms

Dynamic programming

Complete search

Constructive algorithms
Skill types: Dynamic programming

Complete search

Starter code:

Solutions:
from itertools import permutations as perm
import io
import os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m) = map(int, input().split())
s = input().decode('utf-8')[:n]
pre = [[int(s[i] != pat[i % 3]) for i in range(n)] for pat in perm('abc')]
for psum in pre:
	for i in range(1, n):
		psum[i] += psum[i - 1]
for _ in range(m):
	(l, r) = map(int, input().split())
	l -= 1
	mn = 10 ** 9
	for psum in pre:
		res = psum[r - 1]
		if l > 0:
			res -= psum[l - 1]
		mn = min(mn, res)
	print(mn)


(length, count) = map(int, input().split())
string = input()
pref = []
for s in ['abc', 'acb', 'bca', 'cab', 'cba', 'bac']:
	pref_sum = [0] * (length + 1)
	for i in range(length):
		pref_sum[i + 1] = pref_sum[i] + int(string[i] != s[i % 3])
	pref.append(tuple(pref_sum))
ans = [0] * count
for i in range(count):
	(a, b) = map(int, input().split())
	ans[i] = str(min([el[b] - el[a - 1] for el in pref]))
print('\n'.join(ans))


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
st = list(input())
a0 = [0]
a1 = [0]
a2 = [0]
b0 = [0]
b1 = [0]
b2 = [0]
c0 = [0]
c1 = [0]
c2 = [0]
a = [0, 0, 0]
b = [0, 0, 0]
c = [0, 0, 0]
for i in range(n):
	if st[i] == 'a':
		a[i % 3] += 1
	if st[i] == 'b':
		b[i % 3] += 1
	if st[i] == 'c':
		c[i % 3] += 1
	a0.append(a[0])
	a1.append(a[1])
	a2.append(a[2])
	b0.append(b[0])
	b1.append(b[1])
	b2.append(b[2])
	c0.append(c[0])
	c1.append(c[1])
	c2.append(c[2])
for _ in range(m):
	(l, r) = map(int, input().split())
	l -= 1
	ans1 = a1[r] + a2[r] + b0[r] + b2[r] + c0[r] + c1[r] - (a1[l] + a2[l] + b0[l] + b2[l] + c0[l] + c1[l])
	ans2 = a1[r] + a2[r] + b0[r] + b1[r] + c0[r] + c2[r] - (a1[l] + a2[l] + b0[l] + b1[l] + c0[l] + c2[l])
	ans3 = a0[r] + a2[r] + b1[r] + b2[r] + c0[r] + c1[r] - (a0[l] + a2[l] + b1[l] + b2[l] + c0[l] + c1[l])
	ans4 = a0[r] + a1[r] + b1[r] + b2[r] + c0[r] + c2[r] - (a0[l] + a1[l] + b1[l] + b2[l] + c0[l] + c2[l])
	ans5 = a0[r] + a2[r] + b0[r] + b1[r] + c1[r] + c2[r] - (a0[l] + a2[l] + b0[l] + b1[l] + c1[l] + c2[l])
	ans6 = a0[r] + a1[r] + b0[r] + b2[r] + c1[r] + c2[r] - (a0[l] + a1[l] + b0[l] + b2[l] + c1[l] + c2[l])
	print(min(ans1, ans2, ans3, ans4, ans5, ans6))


import sys
(length, count) = map(int, input().split())
string = input()
pref = []
for s in ['abc', 'acb', 'bca', 'cab', 'cba', 'bac']:
	pref_sum = [0] * (length + 1)
	for i in range(length):
		pref_sum[i + 1] = pref_sum[i] + int(string[i] != s[i % 3])
	pref.append(tuple(pref_sum))
ans = [0] * count
for i in range(count):
	(a, b) = map(int, sys.stdin.readline().split())
	ans[i] = str(min([el[b] - el[a - 1] for el in pref]))
sys.stdout.write('\n'.join(ans))


from io import BytesIO, IOBase
import sys
import math
import os
import heapq
from collections import defaultdict, deque
from math import ceil
from bisect import bisect_left, bisect_left
from time import perf_counter
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def mint():
	return map(int, input().split())

def mfloat():
	return map(float, input().split())

def intin():
	return int(input())

def solve():
	(n, m) = map(int, input().split())
	s = input()
	dist = [[0] * n for i in range(6)]
	for (idx, pattern) in enumerate(['abc', 'acb', 'bac', 'bca', 'cab', 'cba']):
		dist[idx][0] = 0 if pattern[0] == s[0] else 1
		for i in range(1, n):
			dist[idx][i] = dist[idx][i - 1] + (s[i] != pattern[i % 3])
	idx = 0
	for q in range(m):
		(l, r) = map(int, input().split())
		l -= 1
		r -= 1
		ans = math.inf
		for i in range(6):
			ans = min(ans, dist[i][r] - (dist[i][l - 1] if l > 0 else 0))
		print(ans)

def main():
	t = 1
	for _ in range(t):
		solve()
start_time = perf_counter()
main()
print(perf_counter() - start_time, file=sys.stderr)


from math import sqrt, gcd, ceil, floor, log, factorial
from itertools import permutations, combinations
from collections import Counter, defaultdict
import collections, sys, threading
import collections, sys, threading
input = sys.stdin.readline

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def msi():
	return map(str, input().split())

def li():
	return list(mi())
(n, m) = mi()
s = si()
res = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
d = defaultdict(list)
for poss in res:
	d[poss] = [0]
for i in range(n):
	for poss in res:
		d[poss].append(d[poss][-1] + (s[i] != poss[i % 3]))
for i in range(m):
	(l, r) = mi()
	print(min((d[poss][r] - d[poss][l - 1] for poss in res)))


import math
from collections import deque, defaultdict
from math import sqrt, ceil, factorial, floor, inf, gcd, log2
import bisect
import sys
import random
import heapq
from sys import stdout

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
(n, m) = get_ints()
s = input()
possible = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
prefix = [[0], [0], [0], [0], [0], [0]]
for i in range(n):
	for j in range(6):
		prefix[j].append(prefix[j][-1] + (s[i] == possible[j][i % 3]))
for i in range(m):
	(l, r) = get_ints()
	min_ans = 0
	for j in range(6):
		min_ans = max(min_ans, prefix[j][r] - prefix[j][l - 1])
	print(r - l + 1 - min_ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, m) = map(int, input().split())
s = input()
a0 = [0 for i in range(len(s))]
a1 = [0 for i in range(len(s))]
a2 = [0 for i in range(len(s))]
b0 = [0 for i in range(len(s))]
b1 = [0 for i in range(len(s))]
b2 = [0 for i in range(len(s))]
c0 = [0 for i in range(len(s))]
c1 = [0 for i in range(len(s))]
c2 = [0 for i in range(len(s))]
for i in range(len(s)):
	if i > 0:
		a0[i] = a0[i - 1]
		b0[i] = b0[i - 1]
		c0[i] = c0[i - 1]
		a1[i] = a1[i - 1]
		b1[i] = b1[i - 1]
		c1[i] = c1[i - 1]
		a2[i] = a2[i - 1]
		b2[i] = b2[i - 1]
		c2[i] = c2[i - 1]
	if s[i] == 'a':
		if i % 3 == 0:
			a0[i] += 1
		elif i % 3 == 1:
			a1[i] += 1
		else:
			a2[i] += 1
	if s[i] == 'b':
		if i % 3 == 0:
			b0[i] += 1
		elif i % 3 == 1:
			b1[i] += 1
		else:
			b2[i] += 1
	if s[i] == 'c':
		if i % 3 == 0:
			c0[i] += 1
		elif i % 3 == 1:
			c1[i] += 1
		else:
			c2[i] += 1
import math
for i in range(m):
	(x, y) = map(int, input().split())
	if x == 1:
		t1 = [a0[y - 1], b0[y - 1], c0[y - 1]]
		t2 = [a1[y - 1], b1[y - 1], c1[y - 1]]
		t3 = [a2[y - 1], b2[y - 1], c2[y - 1]]
	else:
		t1 = [a0[y - 1] - a0[x - 2], b0[y - 1] - b0[x - 2], c0[y - 1] - c0[x - 2]]
		t2 = [a1[y - 1] - a1[x - 2], b1[y - 1] - b1[x - 2], c1[y - 1] - c1[x - 2]]
		t3 = [a2[y - 1] - a2[x - 2], b2[y - 1] - b2[x - 2], c2[y - 1] - c2[x - 2]]
	total = math.inf
	total = min(t1[1] + t1[2] + t2[0] + t2[2] + t3[1] + t3[0], total)
	total = min(t1[1] + t1[2] + t2[0] + t2[1] + t3[0] + t3[2], total)
	total = min(t1[0] + t1[2] + t2[1] + t2[2] + t3[0] + t3[1], total)
	total = min(t1[0] + t1[2] + t2[0] + t2[1] + t3[1] + t3[2], total)
	total = min(t1[0] + t1[1] + t2[0] + t2[2] + t3[1] + t3[2], total)
	total = min(t1[0] + t1[1] + t2[1] + t2[2] + t3[0] + t3[2], total)
	print(total)


import sys
input = sys.stdin.readline

def process(S, Q):
	diffs = {'a': [[0], [0]], 'b': [[0], [0]], 'c': [[0], [0]]}
	should_dict = {}
	for first in 'abc':
		for diff in [1, 2]:
			for i in range(3):
				T = (first, diff, i)
				should = 'abc'[(ord(first) - ord('a') + diff * i) % 3]
				should_dict[T] = should
	n = len(S)
	for i in range(n):
		c = S[i]
		for first in 'abc':
			for diff in [1, 2]:
				should = should_dict[first, diff, i % 3]
				X = diffs[first][diff - 1][-1]
				if c != should:
					diffs[first][diff - 1].append(X + 1)
				else:
					diffs[first][diff - 1].append(X)
	d = {}
	final = []
	for (l, r) in Q:
		if (l, r) in d:
			final.append(d[l, r])
		else:
			answer = float('inf')
			for first in 'abc':
				for diff in [1, 2]:
					L = diffs[first][diff - 1]
					D1 = L[r]
					D2 = L[l - 1]
					answer = min(answer, D1 - D2)
			d[l, r] = answer
			final.append(answer)
	return final
(n, m) = [int(x) for x in input().split()]
S = input()
Q = []
for i in range(m):
	(l, r) = [int(x) for x in input().split()]
	Q.append([l, r])
answer = process(S, Q)
for x in answer:
	sys.stdout.write(str(x) + '\n')


import atexit, io, sys, collections, math, heapq, fractions, copy, os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, q) = map(int, input().split())
s = list(input())
ps = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
dps = [[0, 0, 0, 0, 0, 0] for ii in range(len(s))]
for i in range(len(ps)):
	cumul = 0
	for j in range(len(s)):
		if s[j] != ps[i][j % 3]:
			cumul += 1
		dps[j][i] = cumul
for _ in range(q):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	ans = v - u + 1
	vv = dps[v]
	uu = dps[u - 1] if u - 1 >= 0 else [0, 0, 0, 0, 0, 0]
	print(min([b - a for (a, b) in zip(uu, vv)]))


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def main():
	(n, m) = map(int, input().split())
	s = list(input())
	patterns = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
	prefixSums = {}
	for pattern in patterns:
		prefix = [0] * (n + 1)
		pIndex = 0
		for (i, char) in enumerate(s):
			cost = 0
			if char != pattern[pIndex]:
				cost += 1
			prefix[i + 1] = prefix[i] + cost
			pIndex += 1
			if pIndex > 2:
				pIndex = 0
		prefixSums[pattern] = prefix
	for _ in range(m):
		(l, r) = map(int, input().split())
		l -= 1
		r -= 1
		result = float('inf')
		for prefix in prefixSums.values():
			result = min(result, prefix[r + 1] - prefix[l])
		print(result)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
s = input()
ss = ['abc', 'acb', 'cba', 'cab', 'bac', 'bca']
dps = []
for i in range(6):
	l = [0]
	x = ss[i]
	y = x * (n // 3) + x[0:n % 3]
	for c in range(n):
		l.append(l[-1] + (s[c] != y[c]))
	dps.append(l)
for _ in range(m):
	(a, b) = map(int, input().split())
	ans = 1000000000.0
	for i in range(6):
		ans = min(dps[i][b] - dps[i][a - 1], ans)
	print(ans)


import sys
input = sys.stdin.readline

def find(n, s, arr):
	j = 0
	ans = [0] * (n + 1)
	for i in range(n):
		if s[i] != arr[j]:
			ans[i + 1] = 1
		ans[i + 1] = ans[i] + ans[i + 1]
		j = (j + 1) % 3
	return ans
(n, m) = map(int, input().split())
s = list(input())
A = [['a', 'b', 'c'], ['a', 'c', 'b'], ['b', 'a', 'c'], ['b', 'c', 'a'], ['c', 'a', 'b'], ['c', 'b', 'a']]
val = []
for arr in A:
	B = find(n, s, arr)
	val.append(B.copy())
for i in range(m):
	(l, r) = map(int, input().split())
	ans = r - l + 1
	for i in range(6):
		ans = min(ans, val[i][r] - val[i][l - 1])
	print(ans)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
s = input()[:-1]
L = []
for si in ['a', 'b', 'c']:
	for sj in ['a', 'b', 'c']:
		for sk in ['a', 'b', 'c']:
			if si != sj and sj != sk and (sk != si):
				l = []
				for i in range(n):
					if i % 3 == 0:
						l.append(si)
					elif i % 3 == 1:
						l.append(sj)
					else:
						l.append(sk)
				L.append(l)
acc = [[0] for _ in range(6)]
for i in range(n):
	for j in range(6):
		acc[j].append(acc[j][-1] + (1 if s[i] != L[j][i] else 0))
for _ in range(m):
	(l, r) = map(int, input().split())
	ans = n
	for i in range(6):
		ans = min(ans, acc[i][r] - acc[i][l - 1])
	print(ans)


import math
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
s = input()
mapped = ['abc', 'cab', 'bca', 'bac', 'acb', 'cba']
dp = []
for j in range(6):
	now = mapped[j]
	o = []
	for i in range(n):
		cnt = 0
		if s[i] != now[i % 3]:
			cnt += 1
		if i:
			cnt += o[-1]
		o.append(cnt)
	dp.append(o)
for i in range(m):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	ans = 10 ** 18
	for i in range(6):
		cnt = dp[i][r]
		if l >= 1:
			cnt -= dp[i][l - 1]
		ans = min(ans, cnt)
	sys.stdout.write(str(ans) + '\n')


from sys import *
(n, m) = map(int, stdin.readline().split())
s = stdin.readline()
perm = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
a = [[], [], [], [], [], []]
for i in range(6):
	for j in range(n):
		if s[j] != perm[i][j % 3]:
			if j == 0:
				a[i].append(1)
			else:
				a[i].append(a[i][-1] + 1)
		elif j == 0:
			a[i].append(0)
		else:
			a[i].append(a[i][-1])
for i in range(m):
	(l, r) = map(int, stdin.readline().split())
	l -= 1
	r -= 1
	if l == 0:
		ans = r - l + 1
		for j in range(6):
			ans = min(ans, a[j][r])
	else:
		ans = r - l + 1
		for j in range(6):
			ans = min(ans, a[j][r] - a[j][l - 1])
	stdout.write(str(ans) + '\n')


from collections import defaultdict, Counter, deque
from math import sqrt, log10, log, floor, factorial
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations
import sys, io, os
input = sys.stdin.readline
inf = float('inf')
mod = 10 ** 9 + 7

def get_list():
	return [int(i) for i in input().split()]

def yn(a):
	print('YES' if a else 'NO')
ceil = lambda a, b: (a + b - 1) // b
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
per = list(permutations([97, 98, 99]))
t = 1
for i in range(t):
	(n, k) = [int(i) for i in input().split()]
	s = [ord(i) for i in input().strip()]
	l = []
	prefix = [[0 for i in range(n)] for i in range(6)]
	for i in range(6):
		for j in range(n):
			if s[j] == per[i][j % 3]:
				prefix[i][j] = prefix[i][j - 1] + 1
			else:
				prefix[i][j] = prefix[i][j - 1]
	for i in range(k):
		(a, b) = [int(i) - 1 for i in input().split()]
		diff = b - a + 1
		maxa = inf
		for j in range(6):
			if a == 0:
				maxa = min(maxa, diff - prefix[j][b])
			else:
				maxa = min(maxa, diff - (prefix[j][b] - prefix[j][a - 1]))
		print(maxa)


import sys
input = sys.stdin.buffer.readline
(n, m) = map(int, input().split())
sst = [0] + list(input().strip())
st = []
for i in sst:
	st.append(chr(i))
arr = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
dp = [[0 for i in range(n + 2)] for j in range(6)]
for i in range(6):
	for j in range(1, n + 1):
		if st[j] != arr[i][(j - 1) % 3]:
			dp[i][j] = dp[i][j - 1] + 1
			continue
		dp[i][j] = dp[i][j - 1]
for i in range(m):
	(l, r) = map(int, input().split())
	mini = float('inf')
	for j in range(6):
		mini = min(mini, dp[j][r] - dp[j][l - 1])
	print(mini)


from __future__ import division, print_function
import bisect
import math
import heapq
import itertools
import sys
from collections import deque
from atexit import register
from collections import Counter
from functools import reduce
if sys.version_info[0] < 3:
	from io import BytesIO as stream
else:
	from io import StringIO as stream
if sys.version_info[0] < 3:

	class dict(dict):

		def items(self):
			return dict.iteritems(self)

		def keys(self):
			return dict.iterkeys(self)

		def values(self):
			return dict.itervalues(self)
	input = raw_input
	range = xrange
	filter = itertools.ifilter
	map = itertools.imap
	zip = itertools.izip

def sync_with_stdio(sync=True):
	global input, flush
	if sync:
		flush = sys.stdout.flush
	else:
		sys.stdin = stream(sys.stdin.read())
		input = lambda : sys.stdin.readline().rstrip('\r\n')
		sys.stdout = stream()
		register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))

def main():
	(n, m) = map(int, input().split())
	s = input()
	abc = [[0 for i in range(n + 1)] for j in range(6)]
	strings = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
	for i in range(6):
		strings[i] = strings[i] * (n // 3 + (n % 3 != 0))
	for i in range(n):
		for j in range(6):
			abc[j][i] = abc[j][i - 1]
			if s[i] != strings[j][i]:
				abc[j][i] += 1
	for i in range(m):
		(l, r) = map(int, input().split())
		l -= 2
		r -= 1
		ans = float('inf')
		for j in range(6):
			ans = min(ans, abc[j][r] - abc[j][l])
		print(ans)
sync_with_stdio(False)
main()


import os
import sys
from io import BytesIO, IOBase

def main():
	(n, m) = map(int, input().split())
	s = input()
	s0 = 'abc'
	s1 = 'bca'
	s2 = 'cab'
	s3 = 'cba'
	s4 = 'acb'
	s5 = 'bac'
	S = [s0, s1, s2, s3, s4, s5]
	pre = [[0], [0], [0], [0], [0], [0]]
	for i in range(n):
		for j in range(6):
			pre[j].append(pre[j][-1] + int(S[j][i % 3] != s[i]))
	qry = [list(map(int, input().split())) for i in range(m)]
	for i in range(m):
		(l, r) = qry[i]
		ans = 100000000
		for i in range(6):
			ans = min(pre[i][r] - pre[i][l - 1], ans)
		print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
s = input().strip('\n')
k = n // 3 + n % 3
ligma = ['abc' * k, 'acb' * k, 'bac' * k, 'bca' * k, 'cba' * k, 'cab' * k]
psa = [[0 for i in range(n + 1)] for j in range(6)]
for i in range(6):
	for j in range(1, n + 1):
		psa[i][j] = psa[i][j - 1] + (ligma[i][j - 1] != s[j - 1])
for i in range(m):
	(l, r) = map(int, input().split())
	ans = float('inf')
	for x in range(6):
		ans = min(ans, psa[x][r] - psa[x][l - 1])
	print(ans)


import sys
input = sys.stdin
output = sys.stdout
inputs = input.readline().strip().split()
N = int(inputs[0])
M = int(inputs[1])
S = input.readline().strip()
SL = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
CL = [[0] * (N + 1) for x in range(6)]
for i in range(6):
	subtotal = 0
	substring = SL[i]
	subCL = CL[i]
	for j in range(N):
		if S[j] != substring[j % 3]:
			subtotal += 1
		subCL[j + 1] = subtotal
for i in range(M):
	y = input.readline().strip().split()
	start = int(y[0])
	end = int(y[1])
	total = N
	for j in range(6):
		a = CL[j][end] - CL[j][start - 1]
		if a < total:
			total = a
	print(total)


(n, m) = map(int, input().split())
s = list(input())
lr = [[int(i) for i in input().split()] for _ in range(m)]
li = [[0] * n for _ in range(6)]
ss = [['a', 'b', 'c'].index(c) for c in s]
c0 = 0
c1 = 1
c2 = 2
for i in range(n):
	d0 = (c0 + i) % 3
	d1 = (c1 + i) % 3
	d2 = (c2 + i) % 3
	d3 = (c0 - i) % 3
	d4 = (c1 - i) % 3
	d5 = (c2 - i) % 3
	if ss[i] != d0:
		li[0][i] = 1
	if ss[i] != d1:
		li[1][i] = 1
	if ss[i] != d2:
		li[2][i] = 1
	if ss[i] != d3:
		li[3][i] = 1
	if ss[i] != d4:
		li[4][i] = 1
	if ss[i] != d5:
		li[5][i] = 1
for ind in range(6):
	for i in range(1, n):
		li[ind][i] += li[ind][i - 1]
for (l, r) in lr:
	l -= 1
	r -= 1
	print(min([li[ind][r] - (li[ind][l - 1] if l > 0 else 0) for ind in range(6)]))


import os, sys, math
from io import BytesIO, IOBase
ip = lambda : input()
it = lambda : int(input())
ma = lambda : map(int, input().split(' '))
li = lambda : list(map(int, input().split(' ')))
mod = 10 ** 9 + 7

def prime(n):
	if n == 1:
		return False
	elif n == 2 or n == 3:
		return True
	else:
		l = int(n ** 0.5)
		i = 2
		f = True
		while i <= l:
			if n % i == 0:
				f = False
				break
			i += 1
		return f

def presum(s, a, n):
	arr = [0] * n
	count = 0
	for i in range(n):
		if s[i] != a[i % 3]:
			count += 1
		arr[i] = count
	return arr

def main():
	(n, m) = ma()
	s = ip()
	a = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
	prefixsum = []
	for i in range(6):
		prefixsum.append(presum(s, a[i], n))
	for q in range(m):
		(l, r) = ma()
		res = mod
		if l == 1:
			for i in range(6):
				x = prefixsum[i][r - 1]
				if x < res:
					res = x
		else:
			for i in range(6):
				x = prefixsum[i][r - 1] - prefixsum[i][l - 2]
				if x < res:
					res = x
		print(res)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from itertools import permutations
import sys
input = sys.stdin.readline
(n, m) = list(map(int, input().split()))
s = list(input().strip())
p = list(permutations('abc'))
all_s = []
for sx in p:
	temp = []
	all_s.append([sx[x % 3] for x in range(n)])
dp = {i: [0] * n for i in range(6)}
s_dp = {i: [0] * n for i in range(6)}
for i in range(0, 6):
	for j in range(0, n):
		if all_s[i][j] != s[j]:
			dp[i][j] = 1
		if j == 0:
			s_dp[i][j] = dp[i][j]
		else:
			s_dp[i][j] = dp[i][j] + s_dp[i][j - 1]
for _ in range(m):
	(u, v) = list(map(int, input().split()))
	u -= 1
	v -= 1
	ans = 10000000000.0
	for i in range(0, 6):
		if u == 0:
			ans = min(ans, s_dp[i][v])
		else:
			ans = min(ans, s_dp[i][v] - s_dp[i][u - 1])
	print(ans)


from sys import stdin
from itertools import accumulate
input = stdin.readline
(n, m) = map(int, input().split())
s = list(input().rstrip())
test1 = 'abc' * n
test2 = 'acb' * n
test3 = 'bac' * n
test4 = 'bca' * n
test5 = 'cab' * n
test6 = 'cba' * n
test = [test1, test2, test3, test4, test5, test6]
raw = [[-1 for x in range(n)] for y in range(6)]
pref = [[-1 for x in range(n)] for y in range(6)]
for j in range(6):
	raw[j] = [0 if test[j][i] == s[i] else 1 for i in range(n)]
for i in range(6):
	pref[i] = list(accumulate(raw[i]))
for _ in range(m):
	(l, r) = map(int, input().split())
	ans = min(pref[0][r - 1] - pref[0][l - 1] + raw[0][l - 1], pref[1][r - 1] - pref[1][l - 1] + raw[1][l - 1], pref[2][r - 1] - pref[2][l - 1] + raw[2][l - 1], pref[3][r - 1] - pref[3][l - 1] + raw[3][l - 1], pref[4][r - 1] - pref[4][l - 1] + raw[4][l - 1], pref[5][r - 1] - pref[5][l - 1] + raw[5][l - 1])
	print(ans)


import sys
input = sys.stdin.readline

def give(l, n, s):
	pr = [0]
	k = 0
	for i in range(n):
		if l[i] != s[k]:
			pr.append(pr[-1] + 1)
		else:
			pr.append(pr[-1])
		k = (k + 1) % 3
	return pr
(n, m) = map(int, input().split())
l = input()
s1 = 'bac'
pr1 = give(l, n, s1)
s2 = 'bca'
pr2 = give(l, n, s2)
s3 = 'acb'
pr3 = give(l, n, s3)
s4 = 'abc'
pr4 = give(l, n, s4)
s5 = 'cab'
pr5 = give(l, n, s5)
s6 = 'cba'
pr6 = give(l, n, s6)
res = []
for i in range(m):
	(l, r) = map(int, input().split())
	res.append(min(pr1[r] - pr1[l - 1], pr2[r] - pr2[l - 1], pr3[r] - pr3[l - 1], pr4[r] - pr4[l - 1], pr5[r] - pr5[l - 1], pr6[r] - pr6[l - 1]))
print(*res)


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
s = input()
ss = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
l = []
for i in range(6):
	x = ss[i]
	y = n // 3 * x + x[0:n % 3]
	ll = [0]
	for i in range(n):
		ll.append(ll[i] + (s[i] != y[i]))
	l.append(ll)
for _ in range(q):
	(u, r) = map(int, input().split())
	ans = 1000000000.0
	for i in range(6):
		ans = min(l[i][r] - l[i][u - 1], ans)
	print(ans)


import sys
from sys import stdin
ty = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
(n, m) = map(int, stdin.readline().split())
s = list(stdin.readline()[:-1])
dp = [[0] * (n + 1) for i in range(6)]
for c in range(6):
	for i in range(n):
		if s[i] != ty[c][i % 3]:
			dp[c][i + 1] = dp[c][i] + 1
		else:
			dp[c][i + 1] = dp[c][i]
ANS = []
for loop in range(m):
	(l, r) = map(int, stdin.readline().split())
	ans = float('inf')
	for c in range(6):
		ans = min(ans, dp[c][r] - dp[c][l - 1])
	ANS.append(str(ans))
print('\n'.join(ANS))


from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
s = input()
arb = [[] for _ in range(6)]
b = ['aabbcc', 'bcacab', 'cbcaba']
for i in range(n):
	i_mod = i % 3
	for j in range(6):
		if s[i] != b[i_mod][j]:
			arb[j].append(i)
for _ in range(m):
	(l, r) = map(lambda z: int(z) - 1, input().split())
	minim = float('inf')
	for a in arb:
		x = bisect_left(a, l)
		y = bisect_right(a, r)
		minim = min(minim, y - x)
	print(minim)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if not True else 1):
	(n, m) = map(int, input().split())
	s = input()
	pre = [[0] for i in range(9)]
	for i in range(n):
		c = s[i]
		for j in range(9):
			pre[j] += [pre[j][-1]]
		if i % 3 == 0:
			if c == 'a':
				pre[0][-1] += 1
			if c == 'b':
				pre[3][-1] += 1
			if c == 'c':
				pre[6][-1] += 1
		if i % 3 == 1:
			if c == 'a':
				pre[1][-1] += 1
			if c == 'b':
				pre[4][-1] += 1
			if c == 'c':
				pre[7][-1] += 1
		if i % 3 == 2:
			if c == 'a':
				pre[2][-1] += 1
			if c == 'b':
				pre[5][-1] += 1
			if c == 'c':
				pre[8][-1] += 1
	for i in range(m):
		(l, r) = map(int, input().split())
		x = [pre[j][r] - pre[j][l - 1] for j in range(9)]
		count = max(x[0] + x[4] + x[8], x[0] + x[5] + x[7], x[1] + x[3] + x[8], x[1] + x[5] + x[6], x[2] + x[3] + x[7], x[2] + x[4] + x[6])
		print(r - l + 1 - count)


from collections import defaultdict, Counter, deque
from math import sqrt, log10, log, floor, factorial
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations
import sys, io, os
input = sys.stdin.readline
inf = float('inf')
mod = 10 ** 9 + 7

def get_list():
	return [int(i) for i in input().split()]

def yn(a):
	print('YES' if a else 'NO')
ceil = lambda a, b: (a + b - 1) // b
per = list(permutations([97, 98, 99]))
t = 1
for i in range(t):
	(n, k) = [int(i) for i in input().split()]
	s = [ord(i) for i in input().strip()]
	l = []
	prefix = [[0 for i in range(n)] for i in range(6)]
	for i in range(6):
		for j in range(n):
			if s[j] == per[i][j % 3]:
				prefix[i][j] = prefix[i][j - 1] + 1
			else:
				prefix[i][j] = prefix[i][j - 1]
	for i in range(k):
		(a, b) = [int(i) - 1 for i in input().split()]
		diff = b - a + 1
		maxa = inf
		for j in range(6):
			if a == 0:
				maxa = min(maxa, diff - prefix[j][b])
			else:
				maxa = min(maxa, diff - (prefix[j][b] - prefix[j][a - 1]))
		print(maxa)


import sys
import math
import random
import heapq
input = sys.stdin.readline

def pow(a, n, m):
	if n == 0:
		return 1
	x = pow(a, n // 2, m)
	if n % 2 == 0:
		return x * x % m
	else:
		return x * x * a % m

def gcd(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a

def bs(arr, le, ri):
	l = 0
	arr.sort()
	r = len(arr) - 1
	ans = 10000000
	while l <= r:
		m = (l + r) // 2
		if arr[m] >= le and arr[m] <= ri:
			ans = arr[m]
			r = m - 1
		elif arr[m] < le:
			l = m + 1
		else:
			r = m - 1
	return ans

def fun(s1, s2, r1, r2, c, s, ans):
	if c >= 10:
		return
	elif s1 > s2:
		if s1 - s2 > r2:
			ans[0] = min(ans[0], c)
			return
	elif s2 > s1:
		if s2 - s1 > r1:
			ans[0] = min(ans[0], c)
			return
	if c % 2 == 0:
		r1 -= 1
		if s[c] == '1':
			s1 += 1
			fun(s1, s2, r1, r2, c + 1, s, ans)
		elif s[c] == '0':
			fun(s1, s2, r1, r2, c + 1, s, ans)
		else:
			fun(s1, s2, r1, r2, c + 1, s, ans)
			s1 += 1
			fun(s1, s2, r1, r2, c + 1, s, ans)
	else:
		r2 -= 1
		if s[c] == '1':
			s2 += 1
			fun(s1, s2, r1, r2, c + 1, s, ans)
		elif s[c] == '0':
			fun(s1, s2, r1, r2, c + 1, s, ans)
		else:
			fun(s1, s2, r1, r2, c + 1, s, ans)
			s2 += 1
			fun(s1, s2, r1, r2, c + 1, s, ans)
t = 1
while t > 0:
	(n, m) = map(int, input().split())
	s = input().strip()
	l = ['abc', 'acb', 'bca', 'bac', 'cba', 'cab']
	c = [[0] for i in range(6)]
	for i in range(6):
		for j in range(n):
			x = c[i][-1]
			if s[j] != l[i][j % 3]:
				x += 1
			c[i].append(x)
	for i in range(m):
		(a, b) = map(int, input().split())
		ans = n
		for j in range(6):
			ans = min(ans, c[j][b] - c[j][a - 1])
		print(ans)
	t -= 1


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, m) = [int(x) for x in input().split()]
s = input()
query = []
for i in range(m):
	query.append((int(x) - 1 for x in input().split()))

def gen(st):
	(a, b, c) = st
	arr = ['' for x in range(n)]
	for i in range(0, n, 3):
		arr[i] = a
	for i in range(1, n, 3):
		arr[i] = b
	for i in range(2, n, 3):
		arr[i] = c
	ans = [0 for x in range(n)]
	if arr[0] != s[0]:
		ans[0] += 1
	for i in range(1, n):
		if s[i] != arr[i]:
			ans[i] = ans[i - 1] + 1
		else:
			ans[i] = ans[i - 1]
	return ans
a = []
a.append(gen('abc'))
a.append(gen('cab'))
a.append(gen('bca'))
a.append(gen('cba'))
a.append(gen('bac'))
a.append(gen('acb'))

def solve(arr, l, r):
	if l == 0:
		return arr[r]
	else:
		return arr[r] - arr[l - 1]
for i in range(m):
	(l, r) = query[i]
	output = 10 ** 7
	for i in range(6):
		output = min(output, solve(a[i], l, r))
	sys.stdout.write(str(output) + '\n')


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
s = list(input())[:-1]
for i in range(n):
	s[i] = ord(s[i]) - 97
x = [i % 3 for i in range(n)]
y = [(i + 1) % 3 for i in range(n)]
z = [(i + 2) % 3 for i in range(n)]
a = [i % 3 for i in range(n, 0, -1)]
b = [(i + 1) % 3 for i in range(n, 0, -1)]
c = [(i + 2) % 3 for i in range(n, 0, -1)]
sx = [0] * (n + 1)
sy = [0] * (n + 1)
sz = [0] * (n + 1)
sa = [0] * (n + 1)
sb = [0] * (n + 1)
sc = [0] * (n + 1)
for i in range(n):
	sx[i] = sx[i - 1]
	if x[i] != s[i]:
		sx[i] += 1
	sy[i] = sy[i - 1]
	if y[i] != s[i]:
		sy[i] += 1
	sz[i] = sz[i - 1]
	if z[i] != s[i]:
		sz[i] += 1
	sa[i] = sa[i - 1]
	if a[i] != s[i]:
		sa[i] += 1
	sb[i] = sb[i - 1]
	if b[i] != s[i]:
		sb[i] += 1
	sc[i] = sc[i - 1]
	if c[i] != s[i]:
		sc[i] += 1

def get(l, r):
	res = 10 ** 18
	res = min(res, sx[r] - sx[l - 1])
	res = min(res, sy[r] - sy[l - 1])
	res = min(res, sz[r] - sz[l - 1])
	res = min(res, sa[r] - sa[l - 1])
	res = min(res, sb[r] - sb[l - 1])
	res = min(res, sc[r] - sc[l - 1])
	return res
for _ in range(m):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	print(get(l, r))


from collections import defaultdict as dd
import math
import sys
input = sys.stdin.readline

def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return map(int, input().split())

def lm():
	return list(map(int, input().split()))

def solve():
	(n, m) = mi()
	s = input()
	patters = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
	pattern_costs = []
	for (i, pattern) in enumerate(patters):
		pattern_cost = [0]
		cost = 0
		for j in range(len(s)):
			if not pattern[j % 3] == s[j]:
				cost += 1
			pattern_cost.append(cost)
		pattern_costs.append(pattern_cost)
	for i in range(m):
		(l, r) = mi()
		best = l + r
		for p in pattern_costs:
			cur = p[r] - p[l - 1]
			best = min(cur, best)
		print(best)
q = 1
for _ in range(q):
	solve()


def main():
	mod = 1000000007
	tc = 1
	for _ in range(tc):
		(n, m) = ria()
		s = rs()
		poss = ['abc' * n, 'acb' * n, 'bca' * n, 'bac' * n, 'cab' * n, 'cba' * n]
		z = []

		def zapper(t):
			pref = [0]
			ps = 0
			for i in range(n):
				if s[i] != t[i]:
					ps += 1
				pref.append(ps)
			return pref
		for t in poss:
			z.append(zapper(t))
		for i in range(m):
			(l, r) = ria()
			ans = INF
			for j in z:
				ans = min(ans, j[r] - j[l - 1])
			wi(ans)

def rant():
	return 'AAAAAAAAAAAAAAAAARRRGHHHHHHHHHHHHHHHHHHHHHHHH'

def SieveOfEratosthenes(limit):
	isPrime = [True] * (limit + 1)
	isPrime[0] = isPrime[1] = False
	primes = []
	for i in range(2, limit + 1):
		if not isPrime[i]:
			continue
		primes += [i]
		for j in range(i * i, limit + 1, i):
			isPrime[j] = False
	return primes

def memodict(f):

	class memodict(dict):

		def __missing__(self, key):
			ret = self[key] = f(key)
			return ret
	return memodict().__getitem__

def pollard_rho(n):
	if n & 1 == 0:
		return 2
	if n % 3 == 0:
		return 3
	s = (n - 1 & 1 - n).bit_length() - 1
	d = n >> s
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		p = pow(a, d, n)
		if p == 1 or p == n - 1 or a % n == 0:
			continue
		for _ in range(s):
			prev = p
			p = p * p % n
			if p == 1:
				return math.gcd(prev - 1, n)
			if p == n - 1:
				break
		else:
			for i in range(2, n):
				(x, y) = (i, (i * i + 1) % n)
				f = math.gcd(abs(x - y), n)
				while f == 1:
					(x, y) = ((x * x + 1) % n, (y * y + 1) % n)
					y = (y * y + 1) % n
					f = math.gcd(abs(x - y), n)
				if f != n:
					return f
	return n

@memodict
def prime_factors(n):
	if n <= 1:
		return Counter()
	f = pollard_rho(n)
	return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)

def distinct_factors(n):
	factors = [1]
	for (p, exp) in prime_factors(n).items():
		factors += [p ** i * factor for factor in factors for i in range(1, exp + 1)]
	return factors

def all_factors(n):
	(small, large) = ([], [])
	for i in range(1, int(n ** 0.5) + 1, 2 if n & 1 else 1):
		if not n % i:
			small.append(i)
			large.append(n // i)
	if small[-1] == large[-1]:
		large.pop()
	large.reverse()
	small.extend(large)
	return small

def make_nCr_mod(max_n=2 * 10 ** 5, mod=10 ** 9 + 7):
	max_n = min(max_n, mod - 1)
	(fact, inv_fact) = ([0] * (max_n + 1), [0] * (max_n + 1))
	fact[0] = 1
	for i in range(max_n):
		fact[i + 1] = fact[i] * (i + 1) % mod
	inv_fact[-1] = pow(fact[-1], mod - 2, mod)
	for i in reversed(range(max_n)):
		inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod

	def nCr_mod(n, r):
		res = 1
		while n or r:
			(a, b) = (n % mod, r % mod)
			if a < b:
				return 0
			res = res * fact[a] % mod * inv_fact[b] % mod * inv_fact[a - b] % mod
			n //= mod
			r //= mod
		return res
	return nCr_mod

class DisjointSetUnion:

	def __init__(self, n):
		self.parent = [*range(n + 1)]
		self.size = [1] * (n + 1)
		(self.min, self.max) = ([*range(n + 1)], [*range(n + 1)])
		self.count = n

	def get(self, a):
		if self.parent[a] == a:
			return a
		x = a
		while a != self.parent[a]:
			a = self.parent[a]
		while x != self.parent[x]:
			(self.parent[x], x) = (a, self.parent[x])
		return a

	def union(self, a, b):
		(a, b) = (self.get(a), self.get(b))
		if a != b:
			if self.size[a] > self.size[b]:
				(a, b) = (b, a)
			self.parent[a] = b
			self.size[b] += self.size[a]
			self.min[b] = min(self.min[a], self.min[b])
			self.max[b] = max(self.max[a], self.max[b])
			self.count -= 1

	def count_sets(self):
		return self.count

class SegmentTree:

	def __init__(self, data, default=0, func=max):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		stop += 1
		start += self._size
		stop += self._size
		res_left = res_right = self._default
		while start < stop:
			if start & 1:
				res_left = self._func(res_left, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res_right = self._func(self.data[stop], res_right)
			start >>= 1
			stop >>= 1
		return self._func(res_left, res_right)

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SparseTable:

	def __init__(self, data, func=min):
		self.func = func
		self._data = _data = [list(data)]
		(i, n) = (1, len(_data[0]))
		while 2 * i <= n:
			prev = _data[-1]
			_data.append([func(prev[j], prev[j + i]) for j in range(n - 2 * i + 1)])
			i <<= 1

	def query(self, start, stop):
		depth = (stop + 1 - start).bit_length() - 1
		return self.func(self._data[depth][start], self._data[depth][stop + 1 - (1 << depth)])

	def __getitem__(self, idx):
		return self._data[0][idx]

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))
import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from math import log2
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest
INF = 999999999999999999999999
alphabets = 'abcdefghijklmnopqrstuvwxyz'

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
starttime = datetime.datetime.now()
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
main()
endtime = datetime.datetime.now()
time = (endtime - starttime).total_seconds() * 1000
if os.path.exists('input.txt'):
	print('Time:', time, 'ms')


from sys import stdin
input = stdin.readline

def f(s, q):
	perm = ['abc', 'bca', 'acb', 'bac', 'cab', 'cba']
	res = [i[1] - i[0] + 1 for i in q]
	for word in perm:
		pref = [0] * (len(s) + 1)
		for i in range(len(s)):
			pref[i + 1] = s[i] != word[i % 3]
		for i in range(1, len(pref)):
			pref[i] += pref[i - 1]
		for (id, (l, r)) in enumerate(q):
			res[id] = min(res[id], pref[r] - pref[l - 1])
	return res
(n, m) = map(int, input().strip().split())
s = input().strip()
q = []
for i in range(m):
	(l, r) = map(int, input().strip().split())
	q.append((l, r))
print(*f(s, q), sep='\n')


import itertools as it, bisect, sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
s = input().strip()
arb = [[i for i in range(n) if s[i] != sq[i % 3]] for sq in it.permutations('abc')]
for _ in range(m):
	(l, r) = map(lambda z: int(z) - 1, input().split())
	minim = float('inf')
	for a in arb:
		(x, y) = (bisect.bisect_left(a, l), bisect.bisect_right(a, r))
		minim = min(minim, y - x)
	print(minim)


from itertools import permutations
import sys
inp = sys.stdin.readline
(n, m) = map(int, inp().split())
s = inp()
li = []
for p in permutations('abc'):
	li.append(0)
	count = 0
	for i in range(n):
		if s[i] != p[i % 3]:
			count += 1
		li.append(count)
for _ in range(m):
	(l, r) = map(int, inp().split())
	ans = 1000000000.0
	for i in range(6):
		ans = min(li[(n + 1) * i + r] - li[(n + 1) * i + l - 1], ans)
	print(ans)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
s = input().rstrip()
ss = [('abc' * n)[:n], ('acb' * n)[:n], ('bac' * n)[:n], ('bca' * n)[:n], ('cab' * n)[:n], ('cba' * n)[:n]]
c = [[0] * (n + 1) for i in range(6)]
for i in range(6):
	si = ss[i]
	for j in range(n):
		if s[j] != si[j]:
			c[i][j + 1] += 1
	for j in range(n):
		c[i][j + 1] += c[i][j]
for _ in range(m):
	(nl, nr) = map(int, input().split())
	ans = 10 ** 18
	for i in range(6):
		d = c[i][nr] - c[i][nl - 1]
		ans = min(ans, d)
	print(ans)


import sys, os, io
from sys import stdin
import math
from collections import defaultdict
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
alphabets = list('abcdefghijklmnopqrstuvwxyz')
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieveForSmallestPrimeFactor():
	MAXN = 100001
	spf = [0 for i in range(MAXN)]
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, math.ceil(math.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
	return spf

def getPrimeFactorizationLOGN(x):
	spf = sieveForSmallestPrimeFactor()
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def si():
	return input()

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
	input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, m) = li()
s = list(si())
a = [0] * n
b = [0] * n
c = [0] * n
d = [0] * n
e = [0] * n
f = [0] * n
l = ['a', 'b', 'c']
for i in range(n):
	if s[i] == l[i % 3]:
		a[i] += 1
	if i > 0:
		a[i] += a[i - 1]
l = ['b', 'c', 'a']
for i in range(n):
	if s[i] == l[i % 3]:
		b[i] += 1
	if i > 0:
		b[i] += b[i - 1]
l = ['c', 'b', 'a']
for i in range(n):
	if s[i] == l[i % 3]:
		c[i] += 1
	if i > 0:
		c[i] += c[i - 1]
l = ['a', 'c', 'b']
for i in range(n):
	if s[i] == l[i % 3]:
		d[i] += 1
	if i > 0:
		d[i] += d[i - 1]
l = ['b', 'a', 'c']
for i in range(n):
	if s[i] == l[i % 3]:
		e[i] += 1
	if i > 0:
		e[i] += e[i - 1]
l = ['c', 'a', 'b']
for i in range(n):
	if s[i] == l[i % 3]:
		f[i] += 1
	if i > 0:
		f[i] += f[i - 1]
a = [0] + a
b = [0] + b
c = [0] + c
d = [0] + d
e = [0] + e
f = [0] + f
for i in range(m):
	(le, ri) = li()
	x = ri - le + 1
	le -= 1
	ans = float('inf')
	ans = min(ans, x - (a[ri] - a[le]))
	ans = min(ans, x - (b[ri] - b[le]))
	ans = min(ans, x - (c[ri] - c[le]))
	ans = min(ans, x - (d[ri] - d[le]))
	ans = min(ans, x - (e[ri] - e[le]))
	ans = min(ans, x - (f[ri] - f[le]))
	print(ans)


(n, m) = map(int, input().split())
s = input()
s0 = 'abc'
s1 = 'bca'
s2 = 'cab'
s3 = 'cba'
s4 = 'acb'
s5 = 'bac'
S = [s0, s1, s2, s3, s4, s5]
pre = [[0], [0], [0], [0], [0], [0]]
for i in range(n):
	for j in range(6):
		pre[j].append(pre[j][-1] + int(S[j][i % 3] != s[i]))
qry = [list(map(int, input().split())) for i in range(m)]
for i in range(m):
	(l, r) = qry[i]
	ans = 100000000
	for i in range(6):
		ans = min(pre[i][r] - pre[i][l - 1], ans)
	print(ans)


from math import *
from collections import *
from functools import *
from bisect import *
from itertools import *
from heapq import *
import sys
inf = float('inf')
ninf = -float('inf')
ip = sys.stdin.readline
alphal = 'abcdefghijklmnopqrstuvwxyz'
alphau = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
mod = 10 ** 9 + 7

def ipl():
	return list(map(int, ip().split()))

def ipn():
	return int(ip())

def ipf():
	return float(ip())

def solve():
	(n, m) = ipl()
	s = ip()
	dp = []
	for p in permutations('abc'):
		ndp = [0] * (n + 1)
		for i in range(n):
			ndp[i + 1] = ndp[i] + (s[i] != p[i % 3])
		dp.append(ndp)
	for _ in range(m):
		(l, r) = ipl()
		re = inf
		for i in range(6):
			re = min(re, dp[i][r] - dp[i][l - 1])
		print(re)
t = 1
for _ in range(t):
	solve()


from itertools import product
import itertools
import math
import sys
import heapq
from collections import deque
MOD = 1000000000007

def find(parent, i):
	if parent[i] != i:
		parent[i] = find(parent, parent[i])
	return parent[i]

def union(parent, rank, xx, yy):
	x = find(parent, xx)
	y = find(parent, yy)
	if rank[x] > rank[y]:
		parent[y] = x
	elif rank[y] > rank[x]:
		parent[x] = y
	else:
		parent[y] = x
		rank[x] += 1
ans = 0
x = 0
y = 0
(n, m) = list(map(int, sys.stdin.readline().strip().split()))
s = sys.stdin.readline().strip()
k = len(s)
a = [[0 for i in range(3)] for _ in range(3)]
l = [[0, 0, 0, 0, 0, 0, 0, 0, 0]]
d = {'a': 0, 'b': 1, 'c': 2}
for i in range(n):
	c = d[s[i]]
	k = l[-1].copy()
	k[c + 3 * (i % 3)] += 1
	l.append(k)
for _ in range(m):
	(r, q) = list(map(int, sys.stdin.readline().strip().split()))
	a = []
	for i in range(9):
		a.append(l[q][i] - l[r - 1][i])
	pp = [(0, 4, 8), (0, 5, 7), (1, 3, 8), (1, 5, 6), (2, 4, 6), (2, 3, 7)]
	ans = 0
	for (t1, t2, t3) in pp:
		ans = max(a[t1] + a[t2] + a[t3], ans)
	print(q - r + 1 - ans)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from collections import Counter
from collections import defaultdict as dd
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
stdmap = lambda : map(int, stdstr().split())
stdarr = lambda : list(map(int, stdstr().split()))
mod = 1000000007
(n, m) = stdmap()
s = input()
check = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
mi = float('inf')
str = ''
pref = [[0 for _ in range(n + 1)] for __ in range(6)]
for i in range(6):
	for j in range(n):
		if s[j] != check[i][j % 3]:
			pref[i][j + 1] = pref[i][j] + 1
		else:
			pref[i][j + 1] = pref[i][j]
for i in range(m):
	(l, r) = stdmap()
	res = float('inf')
	for j in range(6):
		curr = pref[j][r] - pref[j][l - 1]
		res = min(res, curr)
	print(res)


import sys
from itertools import accumulate

def rall():
	return sys.stdin.readlines()

def rl():
	return sys.stdin.readline().strip()

def rl_types(types):
	str_list = [x for x in sys.stdin.readline().strip().split(' ')]
	return [types[i](str_list[i]) for i in range(len(str_list))]

def pr(something):
	sys.stdout.write(str(something) + '\n')

def pra(array):
	sys.stdout.write(' '.join([str(x) for x in array]) + '\n')

def solve(array):
	return array
(n, m) = [int(x) for x in rl().split(' ')]
s = rl()
VALID_SHORTS = set(['a', 'b', 'c', 'ab', 'ac', 'ba', 'bc', 'ca', 'cb', 'abc', 'bca', 'cab', 'acb', 'bac', 'cba'])
COSTS_SHORTS = {'aa': 1, 'bb': 1, 'cc': 1, 'aaa': 2, 'bbb': 2, 'ccc': 2}
SEQS = ['abc', 'bca', 'cab', 'acb', 'bac', 'cba']
CONFLICTS = {}
for seq in SEQS:
	conflict = [0 if c == seq[i % 3] else 1 for (i, c) in enumerate(s)]
	CONFLICTS[seq] = list(accumulate([0, *conflict]))
for _ in range(m):
	(l, r) = map(int, rl().split(' '))
	nchar = r - l + 1
	if nchar <= 3:
		subs = s[l - 1:r]
		if subs in VALID_SHORTS:
			cost = 0
		elif subs in COSTS_SHORTS:
			cost = nchar - 1
		else:
			cost = 1
	else:
		cost = min([CONFLICTS[seq][r] - CONFLICTS[seq][l - 1] for seq in SEQS])
	pr(cost)


import sys
input = sys.stdin.readline
(n, m) = [int(c) for c in input().split()]
s = input()
arr = ['abc', 'bca', 'cab', 'bac', 'acb', 'cba']
a = [[0 for i in range(n + 1)] for i in range(6)]
for i in range(6):
	ss = arr[i] * (n // 3 + 1)
	for j in range(n):
		a[i][j] = 1 if ss[j] != s[j] else 0
		a[i][j] += a[i][j - 1]
for _ in range(m):
	(l, r) = [int(c) for c in input().split()]
	l -= 1
	r -= 1
	ans = float('inf')
	for i in range(6):
		ans = min(ans, a[i][r] - a[i][l - 1])
	print(ans)


from bisect import insort, bisect_right, bisect_left
from sys import stdout, stdin, setrecursionlimit
from heapq import heappush, heappop, heapify
from io import BytesIO, IOBase
from collections import *
from itertools import *
from random import *
from string import *
from queue import *
from math import *
from re import *
from os import *

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))
(graph, mod, szzz) = ({}, 10 ** 9 + 7, lambda : sorted(zzz()))

def getStr():
	return input()

def getInt():
	return int(input())

def listStr():
	return list(input())

def getStrs():
	return input().split()

def isInt(s):
	return '0' <= s[0] <= '9'

def input():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in input().split()]

def output(answer, end='\n'):
	stdout.write(str(answer) + end)

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def getPrimes(N=10 ** 5):
	SN = int(sqrt(N))
	sieve = [i for i in range(N + 1)]
	sieve[1] = 0
	for i in sieve:
		if i > SN:
			break
		if i == 0:
			continue
		for j in range(2 * i, N + 1, i):
			sieve[j] = 0
	prime = [i for i in range(N + 1) if sieve[i] != 0]
	return prime

def primeFactor(n, prime=getPrimes()):
	lst = []
	mx = int(sqrt(n)) + 1
	for i in prime:
		if i > mx:
			break
		while n % i == 0:
			lst.append(i)
			n //= i
	if n > 1:
		lst.append(n)
	return lst
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
daysInMounth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
(n, m) = zzz()
arr = getStr()
abc = []
for i in range(6):
	abc.append([0] * (n + 1))
words = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
temps = [0] * 6
for i in range(n):
	for j in range(6):
		if words[j][i % 3] != arr[i]:
			temps[j] += 1
		abc[j][i + 1] = temps[j]
for i in range(m):
	(l, r) = zzz()
	ans = r - l + 1
	for j in range(6):
		ans = min(ans, abc[j][r] - abc[j][l - 1])
	print(ans)


(n, m) = [int(x) for x in input().split(' ')]
s = input()
per = ['abc', 'cba', 'cab', 'bca', 'acb', 'bac']
dif = []
for j in range(len(per)):
	tmp = [int(per[j][0] != s[0])]
	for i in range(1, n, 1):
		tmp.append(tmp[-1] + (per[j][i % 3] != s[i]))
	dif.append(tmp)
res = ''
for _ in range(m):
	(l, r) = [int(x) for x in input().split(' ')]
	l -= 1
	r -= 1
	if l == 0:
		res += str(min(*list(map(lambda x: x[r], dif)))) + '\n'
	else:
		res += str(min(*list(map(lambda x: x[r] - x[l - 1], dif)))) + '\n'
print(res)


import sys
import itertools

def input():
	return sys.stdin.readline().rstrip()
DXY = [(0, -1), (1, 0), (0, 1), (-1, 0)]

def to_int(char):
	return ord(char) - ord('a')

def main():
	(n, q) = map(int, input().split())
	s = input()
	a = [to_int(char) for char in s]
	Querys = [tuple(map(int, input().split())) for i in range(q)]
	perms = list(itertools.permutations((0, 1, 2)))
	mods = [[0] * (n + 1) for i in range(6)]
	for i in range(1, n + 1):
		for mod in range(6):
			mods[mod][i] = mods[mod][i - 1] + (perms[mod][(i - 1) % 3] != a[i - 1])
	for (l, r) in Querys:
		ans = min((mods[mod][r] - mods[mod][l - 1] for mod in range(6)))
		print(ans)
	return 0
main()


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
S = input().strip()
DP = [[0] * (n + 5) for i in range(6)]
SX = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
for i in range(n):
	for j in range(6):
		if SX[j][i % 3] == S[i]:
			DP[j][i] = DP[j][i - 1]
		else:
			DP[j][i] = DP[j][i - 1] + 1
for i in range(m):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	ANS = 1 << 30
	for j in range(6):
		ANS = min(ANS, DP[j][r] - DP[j][l - 1])
	print(ANS)


import sys
LI = lambda : list(map(int, sys.stdin.readline().split()))
MI = lambda : map(int, sys.stdin.readline().split())
SI = lambda : sys.stdin.readline().strip('\n')
II = lambda : int(sys.stdin.readline())
from itertools import permutations
(n, m) = MI()
s = SI()
a = 'abc'
dp = {}
p = []
for v in permutations(a):
	v = ''.join(v)
	p.append(v)
	dp[v] = [0] * n
	x = v * (n // 3 + (n % 3 == 0) + 1)
	for i in range(n):
		dp[v][i] += s[i] != x[i]
	for i in range(1, n):
		dp[v][i] += dp[v][i - 1]
for _ in range(m):
	(a, b) = MI()
	print(min((dp[v][b - 1] - (dp[v][a - 2] if a > 1 else 0) for v in p)))


import os
import sys
from itertools import *
from io import BytesIO, IOBase

def lcm(a, b):
	return a * b // gcd(a, b)

def sieve():
	global spf, adj, MAXN
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(2, MAXN):
		if i * i > MAXN:
			break
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def getdistinctFactorization(n):
	global adj, spf, MAXN
	for i in range(1, n + 1):
		index = 1
		x = i
		if x != 1:
			adj[i].append(spf[x])
		x = x // spf[x]
		while x != 1:
			if adj[i][index - 1] != spf[x]:
				adj[i].append(spf[x])
				index += 1
			x = x // spf[x]

def printDivisors(n):
	i = 2
	z = [1, n]
	while i <= sqrt(n):
		if n % i == 0:
			if n / i == i:
				z.append(i)
			else:
				z.append(i)
				z.append(n // i)
		i = i + 1
	return z

def create(n, x, f):
	pq = len(bin(n)[2:])
	if f == 0:
		tt = min
	else:
		tt = max
	dp = [[inf] * n for _ in range(pq)]
	dp[0] = x
	for i in range(1, pq):
		for j in range(n - (1 << i) + 1):
			dp[i][j] = tt(dp[i - 1][j], dp[i - 1][j + (1 << i - 1)])
	return dp

def enquiry(l, r, dp, f):
	if l > r:
		return inf if not f else -inf
	if f == 1:
		tt = max
	else:
		tt = min
	pq1 = len(bin(r - l + 1)[2:]) - 1
	return tt(dp[pq1][l], dp[pq1][r - (1 << pq1) + 1])

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	x = []
	for i in range(2, n + 1):
		if prime[i]:
			x.append(i)
	return x

def main():
	(n, m) = map(int, input().split())
	s = input().strip()
	dp = [[0, 0, 0, 0, 0, 0] for i in range(n + 1)]
	c = 0
	for i in permutations(['a', 'b', 'c'], 3):
		i = ''.join(i)
		for j in range(n):
			if s[j] != i[j % 3]:
				dp[j + 1][c] += 1
			if j > 0:
				dp[j + 1][c] += dp[j][c]
		c += 1
	for i in range(m):
		(u, v) = map(int, input().split())
		an = float('inf')
		for j in range(6):
			an = min(abs(dp[v][j] - dp[u - 1][j]), an)
		print(an)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
input = sys.stdin.readline
(N, Q) = map(int, input().split())
S = input()
T = ['abc', 'bca', 'cab', 'cba', 'bac', 'acb']
Cum = [[0] * (N + 1) for _ in range(6)]
for i in range(6):
	for j in range(N):
		if T[i][j % 3] != S[j]:
			Cum[i][j + 1] += 1
	for j in range(N):
		Cum[i][j + 1] += Cum[i][j]
for _ in range(Q):
	(L, R) = map(int, input().split())
	L -= 1
	Ans = 1001001001
	for i in range(6):
		Value = Cum[i][R] - Cum[i][L]
		if Ans > Value:
			Ans = Value
	print(Ans)


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(2 * 10 ** 5 + 10)
write = lambda x: sys.stdout.write(x + '\n')
debug = lambda x: sys.stderr.write(x + '\n')
writef = lambda x: print('{:.12f}'.format(x))
(n, m) = list(map(int, input().split()))
vs = [[0] * n for _ in range(3)]
i = 0
for c in input():
	v = ord(c) - ord('a')
	for vv in range(3):
		if vv == v:
			continue
		vs[vv][i] += 1
	i += 1
for j in range(3):
	for i in range(3, n):
		vs[j][i] = vs[j][i - 3] + vs[j][i]
ans = []
inf = 10 ** 12

def _sub(l, r, v):
	if l > r:
		return 0
	li = vs[v]
	rr = l + (r - l) // 3 * 3
	return li[rr] - (li[l - 3] if l >= 3 else 0)

def sub(l, r):
	res = inf
	for v0 in range(3):
		for v1 in range(3):
			if v0 == v1:
				continue
			v2 = 3 ^ v0 ^ v1
			res = min(res, _sub(l, r, v0) + _sub(l + 1, r, v1) + _sub(l + 2, r, v2))
	return res
for i in range(m):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	val = sub(l, r)
	ans.append(val)
write('\n'.join(map(str, ans)))


import sys
import math
from collections import deque, Counter
from sys import stdin
int1 = lambda x: int(x) - 1
inp = lambda : int(input())
mi = lambda : map(int, input().split())
li = lambda : list(mi())
mi1 = lambda : map(int1, input().split())
li1 = lambda : list(mi1())
mis = lambda : map(str, input().split())
lis = lambda : list(mis())
stinput = lambda : stdin.readline()[:-1]
stinp = lambda : int(stinput())
stmi = lambda : map(int, stdin.readline().split())
stli = lambda : list(stmi())
stmi1 = lambda : map(int1, stdin.readline().split())
stli1 = lambda : list(stmi1())
stmis = lambda : stdin.readline()[:-1]
pr = print
from collections import defaultdict
mod = 10 ** 9 + 7
Mod = 998244353
INF = 10 ** 18
ans = 0
(n, m) = map(int, stdin.readline().split())
k = n + 1
s = stdin.readline()[:-1]
abc = [0] * k
x = 'abc'
cnt = 0
for i in range(n):
	if x[i % 3] != s[i]:
		cnt += 1
	abc[i + 1] = cnt
acb = [0] * k
x = 'acb'
cnt = 0
for i in range(n):
	if x[i % 3] != s[i]:
		cnt += 1
	acb[i + 1] = cnt
bac = [0] * k
x = 'bac'
cnt = 0
for i in range(n):
	if x[i % 3] != s[i]:
		cnt += 1
	bac[i + 1] = cnt
bca = [0] * k
x = 'bca'
cnt = 0
for i in range(n):
	if x[i % 3] != s[i]:
		cnt += 1
	bca[i + 1] = cnt
cab = [0] * k
x = 'cab'
cnt = 0
for i in range(n):
	if x[i % 3] != s[i]:
		cnt += 1
	cab[i + 1] = cnt
cba = [0] * k
x = 'cba'
cnt = 0
for i in range(n):
	if x[i % 3] != s[i]:
		cnt += 1
	cba[i + 1] = cnt
for _ in range(m):
	(x, y) = stmi()
	ans = min([abc[y] - abc[x - 1], acb[y] - acb[x - 1], bac[y] - bac[x - 1], bca[y] - bca[x - 1], cab[y] - cab[x - 1], cba[y] - cba[x - 1]])
	print(ans)


import sys, io, os, math, bisect, heapq
from collections import Counter, deque, defaultdict
try:
	inp = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
except:
	inp = lambda : sys.stdin.readline().encode()
L = lambda : list(map(int, inp().split()))
I = lambda : int(inp())
S = lambda : inp().strip().decode()
C = lambda : inp().split()

def solve():
	(n, q) = L()
	s = S()
	a = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
	dp = [[0 for i in range(n)] for i in range(6)]
	for i in range(6):
		for j in range(n):
			if j:
				dp[i][j] += dp[i][j - 1]
			dp[i][j] += s[j] != a[i][j % 3]
	while q:
		q -= 1
		(l, r) = L()
		l -= 1
		r -= 1
		ans = 10 ** 18
		for i in range(6):
			x = 0
			x += dp[i][r]
			if l:
				x -= dp[i][l - 1]
			ans = min(ans, x)
		print(ans)
for _ in range(1):
	solve()


from sys import *
input = stdin.readline
from bisect import *
import math
from collections import *
import operator
from heapq import *
from itertools import *
inf = 10 ** 18
mod = 10 ** 9 + 7
(n, m) = map(int, input().split())
s = input()[:-1]
arr = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
temp = [[0] for _ in range(6)]
for i in range(n):
	x = i % 3
	for j in range(6):
		if arr[j][x] != s[i]:
			temp[j].append(temp[j][-1] + 1)
		else:
			temp[j].append(temp[j][-1])
for _ in range(m):
	(l, r) = map(int, input().split())
	minn = inf
	for i in range(6):
		minn = min(minn, temp[i][r] - temp[i][l - 1])
	print(minn)


import sys
import os
from sys import stdin
input = stdin.readline
print = sys.stdout.write

def main():
	(n, m) = map(int, input().split())
	s = input()
	shifts = [[0] * (n + 1), [0] * (n + 1), [0] * (n + 1)]
	shifts2 = [[0] * (n + 1), [0] * (n + 1), [0] * (n + 1)]
	alphabet = 'abc'
	alphabet2 = 'acb'
	for i in range(n):
		for j in range(3):
			check = alphabet[(i + j) % 3]
			shifts[j][i + 1] = shifts[j][i]
			if s[i] != check:
				shifts[j][i + 1] += 1
			check2 = alphabet2[(i + j) % 3]
			shifts2[j][i + 1] = shifts2[j][i]
			if s[i] != check2:
				shifts2[j][i + 1] += 1
	for _ in range(m):
		(l, r) = map(int, input().split())
		best = n
		for i in range(3):
			best = min(shifts[i][r] - shifts[i][l - 1], best)
		for i in range(3):
			best = min(shifts2[i][r] - shifts2[i][l - 1], best)
		print(str(best) + '\n')
main()


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m) = map(int, input().split())
s = input().decode()
Pattern = ['abc', 'bac', 'cab', 'acb', 'bca', 'cba']
Match = [[0] * 6 for i in range(n + 1)]
for i in range(n + 1):
	for j in range(6):
		pattern = Pattern[j]
		if i == 0:
			continue
		times = Match[i - 1][j]
		if s[i - 1] != pattern[(i - 1) % 3]:
			times += 1
		Match[i][j] = times
for _ in range(m):
	(l, r) = map(int, input().split())
	prefix1 = Match[l - 1]
	prefix2 = Match[r]
	ans = float('inf')
	for i in range(6):
		ans = min(ans, prefix2[i] - prefix1[i])
	print(ans)


from sys import stdin
input = stdin.readline
cycles = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
(n, m) = [int(x) for x in input().split()]
s = input().rstrip()
prefix_changes = [[0] for _ in range(6)]
for i in range(n):
	k = i % 3
	for j in range(6):
		if s[i] != cycles[j][k]:
			prefix_changes[j].append(prefix_changes[j][-1] + 1)
		else:
			prefix_changes[j].append(prefix_changes[j][-1])
for _ in range(m):
	(l, r) = [int(x) for x in input().split()]
	ans = float('inf')
	for i in range(6):
		x = prefix_changes[i][r] - prefix_changes[i][l - 1]
		ans = min(ans, x)
	print(ans)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())
t = 1
gl = {'a': 0, 'b': 1, 'c': 2}
while t:
	t -= 1
	(n, q) = ma()
	s = st()
	first = [[0, 0, 0]]
	second = [[0, 0, 0]]
	third = [[0, 0, 0]]
	for i in range(len(s)):
		if i % 3 == 0:
			x = first[-1][:]
			if s[i] == 'a':
				first.append([x[0] + 1, x[1], x[2]])
			elif s[i] == 'b':
				first.append([x[0], x[1] + 1, x[2]])
			else:
				first.append([x[0], x[1], x[2] + 1])
			second.append(second[-1])
			third.append(third[-1])
		elif i % 3 == 1:
			x = second[-1][:]
			if s[i] == 'a':
				second.append([x[0] + 1, x[1], x[2]])
			elif s[i] == 'b':
				second.append([x[0], x[1] + 1, x[2]])
			else:
				second.append([x[0], x[1], x[2] + 1])
			first.append(first[-1])
			third.append(third[-1])
		else:
			x = third[-1][:]
			if s[i] == 'a':
				third.append([x[0] + 1, x[1], x[2]])
			elif s[i] == 'b':
				third.append([x[0], x[1] + 1, x[2]])
			else:
				third.append([x[0], x[1], x[2] + 1])
			first.append(first[-1])
			second.append(second[-1])
	for i in range(q):
		(l, r) = ma()
		res = float('inf')
		a = first[r][:]
		b = first[l - 1][:]
		f1 = [a[0] - b[0], a[1] - b[1], a[2] - b[2]]
		a = second[r][:]
		b = second[l - 1][:]
		f2 = [a[0] - b[0], a[1] - b[1], a[2] - b[2]]
		a = third[r][:]
		b = third[l - 1][:]
		f3 = [a[0] - b[0], a[1] - b[1], a[2] - b[2]]
		res = min(res, f1[1] + f1[2] + f2[0] + f2[2] + f3[0] + f3[1], f1[1] + f1[2] + f2[0] + f2[1] + f3[0] + f3[2], f1[0] + f1[2] + f2[1] + f2[2] + f3[0] + f3[1], f1[0] + f1[2] + f2[0] + f2[1] + f3[1] + f3[2], f1[0] + f1[1] + f2[1] + f2[2] + f3[0] + f3[2], f1[0] + f1[1] + f2[0] + f2[2] + f3[1] + f3[2])
		print(res)


import itertools
import sys
input = sys.stdin.readline

def main():
	(n, m) = map(int, input().split())
	s = str(input())
	alphabet = ['a', 'b', 'c']
	kouho = []
	for L in itertools.permutations(alphabet, 3):
		temp = [0]
		for i in range(n):
			plus = 0
			if s[i] != L[i % 3]:
				plus += 1
			temp.append(temp[-1] + plus)
		kouho.append(temp)
	for i in range(m):
		(l, r) = map(int, input().split())
		l -= 1
		ans = pow(10, 6)
		for j in range(6):
			temp = kouho[j][r] - kouho[j][l]
			ans = min(ans, temp)
		print(ans)
main()


from itertools import product, permutations, combinations, accumulate, compress
import os, sys
input = lambda : sys.stdin.buffer.readline().rstrip(b'\r\n')

def dbp(*args, **kwargs):
	print(*args, file=sys.stderr, **kwargs)
a_str = lambda : input().decode('ascii')
get_int_list = lambda : [int(x) for x in input().split()]
join_str = lambda l, ch=' ': ch.join((str(x) for x in l))

def do_thing():
	(n, q) = get_int_list()
	s = input()
	pcpas = []
	for p in permutations(b'abc'):
		pfxa = [0]
		j = 0
		for i in range(n):
			pfxa.append(pfxa[-1] + (1 if p[j] != s[i] else 0))
			j += 1 if j < 2 else -2
		pcpas.append(pfxa)
	dbp(pcpas)

	def querypile():
		cq = 0
		for line in sys.stdin.buffer.read().split(b'\n'):
			yield [int(x) for x in line.split()]
			cq += 1
			if cq >= q:
				break
	ans = []
	for (l, r) in querypile():
		l -= 1
		ans.append(min((pcpa[r] - pcpa[l] for pcpa in pcpas)))
	return join_str(ans, '\n')

def multicase():
	maxcc = int(input().strip())
	for cc in range(maxcc):
		print(do_thing())
print(do_thing())


import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import gcd, log
input = lambda : sys.stdin.readline().rstrip()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
s = 'abc'
t = 'acb'
(n, m) = mi()
S = input()
calc = [[0 for j in range(6)] for i in range(n)]
for i in range(n):
	for j in range(3):
		calc[i][j] = int(s[(i + j) % 3] != S[i])
		if i != 0:
			calc[i][j] += calc[i - 1][j]
	for j in range(3, 6):
		calc[i][j] = int(t[(i + j) % 3] != S[i])
		if i != 0:
			calc[i][j] += calc[i - 1][j]
for _ in range(m):
	(l, r) = mi()
	(l, r) = (l - 1, r - 1)
	res = n
	for j in range(6):
		tmp = calc[r][j]
		if l:
			tmp -= calc[l - 1][j]
		res = min(res, tmp)
	print(res)


import sys
import math
from math import *
import builtins
import collections
import bisect
import os
from io import BytesIO, IOBase

def print(x, end='\n'):
	sys.stdout.write(str(x) + end)

def get_int():
	return int(input())

def get_list_ints():
	return list(map(int, input().split()))

def get_char_list():
	s = input()
	return list(s[:len(s)])

def get_tuple_ints():
	return tuple(map(int, input().split()))

def print_iterable(p):
	print(' '.join(map(str, p)))

def CountFrequency(arr):
	return collections.Counter(arr)

def reverse(s):
	l = len(s)
	for i in range(l // 2):
		(s[i], s[l - i - 1]) = (s[l - i - 1], s[i])
	return s

def binary_search(arr, x):
	low = 0
	high = len(arr) - 1
	mid = 0
	while low <= high:
		mid = (high + low) // 2
		if arr[mid] < x:
			low = mid + 1
		elif arr[mid] > x:
			high = mid - 1
		else:
			return mid
	return high

def lower_bound(arr, x):
	return bisect.bisect_left(arr, x, lo=0, hi=len(arr))

def upper_bound(arr, x):
	return bisect.bisect_right(arr, x, lo=0, hi=len(arr))

def position(x):
	return ord(x) - ord('a') + 1

def pow(a, n):
	if n == 0:
		return 1
	elif n % 2 == 0:
		return pow(a, n // 2) % const * (pow(a, n // 2) % const) % const
	else:
		return pow(a, n // 2) % const * (pow(a, n // 2) % const) * (a % const) % const

def main():
	[n, m] = get_list_ints()
	s = get_char_list()
	pre = [[0 for i in range(n)] for i in range(6)]
	str1 = []
	for i in range(n):
		if i % 3 == 0:
			str1.append('a')
		elif i % 3 == 1:
			str1.append('b')
		else:
			str1.append('c')
	for k in range(n):
		if k == 0:
			if s[0] != str1[0]:
				pre[0][0] = 1
		elif s[k] != str1[k]:
			pre[0][k] = pre[0][k - 1] + 1
		else:
			pre[0][k] = pre[0][k - 1]
	str1 = []
	for i in range(n):
		if i % 3 == 0:
			str1.append('a')
		elif i % 3 == 1:
			str1.append('c')
		else:
			str1.append('b')
	for k in range(n):
		if k == 0:
			if s[0] != str1[0]:
				pre[1][0] = 1
		elif s[k] != str1[k]:
			pre[1][k] = pre[1][k - 1] + 1
		else:
			pre[1][k] = pre[1][k - 1]
	str1 = []
	for i in range(n):
		if i % 3 == 0:
			str1.append('b')
		elif i % 3 == 1:
			str1.append('a')
		else:
			str1.append('c')
	for k in range(n):
		if k == 0:
			if s[0] != str1[0]:
				pre[2][0] = 1
		elif s[k] != str1[k]:
			pre[2][k] = pre[2][k - 1] + 1
		else:
			pre[2][k] = pre[2][k - 1]
	str1 = []
	for i in range(n):
		if i % 3 == 0:
			str1.append('b')
		elif i % 3 == 1:
			str1.append('c')
		else:
			str1.append('a')
	for k in range(n):
		if k == 0:
			if s[0] != str1[0]:
				pre[3][0] = 1
		elif s[k] != str1[k]:
			pre[3][k] = pre[3][k - 1] + 1
		else:
			pre[3][k] = pre[3][k - 1]
	str1 = []
	for i in range(n):
		if i % 3 == 0:
			str1.append('c')
		elif i % 3 == 1:
			str1.append('b')
		else:
			str1.append('a')
	for k in range(n):
		if k == 0:
			if s[0] != str1[0]:
				pre[4][0] = 1
		elif s[k] != str1[k]:
			pre[4][k] = pre[4][k - 1] + 1
		else:
			pre[4][k] = pre[4][k - 1]
	str1 = []
	for i in range(n):
		if i % 3 == 0:
			str1.append('c')
		elif i % 3 == 1:
			str1.append('a')
		else:
			str1.append('b')
	for k in range(n):
		if k == 0:
			if s[0] != str1[0]:
				pre[5][0] = 1
		elif s[k] != str1[k]:
			pre[5][k] = pre[5][k - 1] + 1
		else:
			pre[5][k] = pre[5][k - 1]
	for i in range(m):
		[l, r] = get_list_ints()
		ans = 200001
		if l > 1:
			for i in range(6):
				ans = min(ans, pre[i][r - 1] - pre[i][l - 2])
			print(ans)
		else:
			for i in range(6):
				ans = min(ans, pre[i][r - 1])
			print(ans)
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
from itertools import permutations

def I():
	return int(sys.stdin.readline().rstrip())

def MI():
	return map(int, sys.stdin.readline().rstrip().split())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def LI2():
	return list(map(int, sys.stdin.readline().rstrip()))

def S():
	return sys.stdin.readline().rstrip()

def LS():
	return list(sys.stdin.readline().rstrip().split())

def LS2():
	return list(sys.stdin.readline().rstrip())
(n, m) = MI()
s = S()
A = [[0] * 6 for _ in range(n + 1)]
X = list(permutations(['a', 'b', 'c'], 3))
for j in range(6):
	(a, b, c) = X[j]
	for i in range(1, n + 1):
		A[i][j] = A[i - 1][j]
		char = s[i - 1]
		if i % 3 == 0 and char != a:
			A[i][j] += 1
		elif i % 3 == 1 and char != b:
			A[i][j] += 1
		elif i % 3 == 2 and char != c:
			A[i][j] += 1
for _ in range(m):
	(l, r) = MI()
	ans = 10 ** 18
	for j in range(6):
		ans = min(ans, A[r][j] - A[l - 1][j])
	print(ans)


def read_ints():
	return [int(x) for x in input().split()]
forms = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
(n, m) = read_ints()
s = input()
k = 6
ans = [[0] * n for _ in range(k)]
for j in range(k):
	for i in range(n):
		ans[j][i] = 0 if s[i] == forms[j][i % 3] else 1
		ans[j][i] += 0 if i == 0 else ans[j][i - 1]
jwbs = []
for i in range(m):
	(l, r) = read_ints()
	l -= 1
	r -= 1
	jwb = n
	for j in range(k):
		prev = 0 if l == 0 else ans[j][l - 1]
		jwb = min(jwb, ans[j][r] - prev)
	jwbs.append(str(jwb))
print('\n'.join(jwbs))


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
s = input().rstrip()
data = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
cache = [[0] for _ in range(6)]
k = n // 3 + 1
for i in range(6):
	comp = data[i] * k
	summ = 0
	for j in range(n):
		if s[j] != comp[j]:
			summ += 1
		cache[i].append(summ)
for _ in range(m):
	(a, b) = map(int, input().split())
	ret = int(1000000000.0)
	for i in range(6):
		ret = min(ret, cache[i][b] - cache[i][a - 1])
	print(ret)


import sys
input = sys.stdin.readline

def mp():
	return map(int, input().split())

def lmp():
	return list(map(int, input().split()))

def mps(A):
	return [tuple(map(int, input().split())) for _ in range(A)]
import math
import bisect
from copy import deepcopy as dc
from itertools import accumulate
from collections import Counter, defaultdict, deque

def ceil(U, V):
	return (U + V - 1) // V

def modf1(N, MOD):
	return (N - 1) % MOD + 1
inf = int(1e+20)
mod = int(1000000000.0 + 7)

def make(S):
	m = []
	ans = [0]
	for i in range(n):
		m.append(S[i % 3])
	for i in range(n):
		if m[i] != s[i]:
			ans.append(ans[-1] + 1)
		else:
			ans.append(ans[-1])
	c.append(ans)
(n, Q) = mp()
s = input()[:-1]
c = []
make('abc')
make('bca')
make('cab')
make('acb')
make('bac')
make('cba')
for _ in range(Q):
	(a, b) = mp()
	a -= 1
	ans = inf
	for i in range(6):
		ans = min(ans, c[i][b] - c[i][a])
	print(ans)


def main(n, m, s, query):
	permutation = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
	dp = [[0] * len(permutation) for _ in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(len(permutation)):
			req = permutation[j][(i - 1) % 3]
			dp[i][j] = dp[i - 1][j] + (0 if s[i - 1] == req else 1)
	ans = []
	for (l, r) in query:
		ans.append(min((dp[r][i] - dp[l - 1][i] for i in range(len(permutation)))))
	return ans
t = 1
ans = []
for i in range(t):
	inp = input().split(' ')
	(n, m) = (int(inp[0]), int(inp[1]))
	s = input()
	query = []
	for q in range(m):
		inp = input().split(' ')
		(l, r) = (int(inp[0]), int(inp[1]))
		query.append((l, r))
	ans = main(n, m, s, query)
print('\n'.join((str(i) for i in ans)))


import sys
input = sys.stdin.readline
t = 1
for j in range(t):
	(n, m) = map(int, input().split())
	s = list(input().strip())
	temp = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
	dp = [[0 for x in range(n + 1)] for y in range(6)]
	for x in range(6):
		for y in range(n):
			dp[x][y + 1] = dp[x][y]
			if s[y] != temp[x][y % 3]:
				dp[x][y + 1] += 1
	for i in range(m):
		(l, r) = map(int, input().split())
		ans = dp[0][r] - dp[0][l - 1]
		for x in range(5):
			ans = min(ans, dp[x + 1][r] - dp[x + 1][l - 1])
		print(ans)


from itertools import *
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
s = input()
ps = [list(accumulate((c1 != c2 for (c1, c2) in zip(cycle(pm), s)), initial=0)) for pm in permutations('abc')]
for _ in range(m):
	(l, r) = map(int, input().split())
	print(min((p[r] - p[l - 1] for p in ps)))


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
s = input().strip()
costs = []
possible = 'abc'
for i in range(3):
	for j in range(3):
		if i != j:
			k = 0
			while k == i or k == j:
				k += 1
			pattern = possible[i] + possible[j] + possible[k]
			cost = [0] * (n + 1)
			for i2 in range(n):
				cost[i2] = cost[i2 - 1] + (s[i2] != pattern[i2 % 3])
			costs.append(cost)
for i in range(m):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	ans = 1000000000.0
	for cost in costs:
		ans = min(ans, cost[r] - cost[l - 1])
	print(ans)


import sys
input = sys.stdin.readline

def getP(j):
	if j >= 3:
		l = j - 3
		return 3 + (l + 1) % 3
	else:
		return (j + 1) % 3

def solve(st, n, m):
	pref = [[0] * (n + 1) for i in range(6)]
	match = 'abcacb'
	for j in range(n - 1, -1, -1):
		for i in range(6):
			pref[i][j] = 1 + pref[getP(i)][j + 1]
			if match[i] == st[j]:
				pref[i][j] -= 1

	def get(ind, l, r):
		ln = r - l + 1
		p = None
		if ind >= 3:
			p = 3 + (ind + ln) % 3
		else:
			p = (ind + ln) % 3
		change = pref[ind][l - 1] - pref[p][r]
		return change
	for q in range(m):
		(l, r) = map(int, input().split())
		ans = float('inf')
		for i in range(6):
			ans = min(ans, get(i, l, r))
		print(ans)
(n, m) = map(int, input().split())
st = input().rstrip()
solve(st, n, m)


from sys import stdin
input = stdin.readline
rn = lambda : int(input())
rns = lambda : map(int, input().split())
rl = lambda : list(map(int, input().split()))
rs = lambda : input().strip()
YN = lambda x: print('YES') if x else print('NO')
mod = 10 ** 9 + 7
from itertools import permutations
from math import ceil
(n, m) = rns()
s = rs()
ls = []
for perm in permutations('abc'):
	st = ''
	for i in perm:
		st += i
	comp = int(ceil(n / 3)) * st
	add = []
	for i in range(n):
		if i == 0:
			if s[i] != comp[i]:
				add.append(1)
			else:
				add.append(0)
		elif s[i] != comp[i]:
			add.append(1 + add[-1])
		else:
			add.append(add[-1])
	ls.append(add)
for _ in range(m):
	(l, r) = rns()
	ans = float('inf')
	for test in ls:
		ans = min(ans, test[r - 1] - test[l - 2] if l > 1 else test[r - 1])
	print(ans)


import sys
input = sys.stdin.readline
from itertools import permutations
(n, m) = map(int, input().split())
s = input()[:-1]
k = (n + 2) // 3
A = []
for cand in permutations('abc'):
	x = ''.join(cand)
	t = (x * k)[:n]
	cur = [0]
	for (a, b) in zip(s, t):
		cur.append(cur[-1] + (a != b))
	A.append(cur)
for _ in range(m):
	(a, b) = map(int, input().split())
	ans = float('inf')
	for acc in A:
		cur = acc[b] - acc[a - 1]
		ans = min(ans, cur)
	print(ans)


(n, m) = map(int, input().split())
s = list(input())
a = [0] * (n + 1)
b = [0] * (n + 1)
c = [0] * (n + 1)
d = [0] * (n + 1)
e = [0] * (n + 1)
f = [0] * (n + 1)
(pa, pb, pc, pd, pe, pf) = ('abc', 'bca', 'cab', 'acb', 'cba', 'bac')
for i in range(n):
	if s[i] != pa[i % 3]:
		a[i] += 1
	if s[i] != pb[i % 3]:
		b[i] += 1
	if s[i] != pc[i % 3]:
		c[i] += 1
	if s[i] != pd[i % 3]:
		d[i] += 1
	if s[i] != pe[i % 3]:
		e[i] += 1
	if s[i] != pf[i % 3]:
		f[i] += 1
for i in range(1, n):
	a[i] += a[i - 1]
	b[i] += b[i - 1]
	c[i] += c[i - 1]
	d[i] += d[i - 1]
	e[i] += e[i - 1]
	f[i] += f[i - 1]
ans = []
for _ in range(m):
	(L, R) = map(lambda z: int(z) - 1, input().split())
	ans.append(min(a[R] - a[L - 1], b[R] - b[L - 1], c[R] - c[L - 1], d[R] - d[L - 1], e[R] - e[L - 1], f[R] - f[L - 1]))
print('\n'.join(map(str, ans)))


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
s = input().strip()
A = [[0] * n for _ in range(6)]
B = ['abc', 'acb', 'bac', 'bca', 'cba', 'cab']
for i in range(6):
	pat = B[i]
	for k in range(n):
		if s[k] != pat[k % 3]:
			A[i][k] += 1
		if k >= 1:
			A[i][k] += A[i][k - 1]
for _ in range(m):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	print(min([A[i][r] - (A[i][l - 1] if l >= 1 else 0) for i in range(6)]))


import itertools
from sys import stdin

def input():
	return next(stdin)[:-1]

def readline():
	return map(int, input().split())
(n, m) = readline()
s = input()
periods = list(itertools.permutations('abc'))
c = {p: [0] for p in periods}
for (i, ch) in enumerate(s):
	for p in periods:
		c[p].append(c[p][-1] + (ch != p[i % 3]))
for __ in range(m):
	(l, r) = readline()
	print(min((c[p][r] - c[p][l - 1] for p in periods)))


import itertools
DEBUG = 0
if DEBUG == 1:
	data = open('sample1.in', 'r')

def readline():
	if DEBUG == 1:
		return data.readline().strip('\r\n')
	else:
		try:
			return input().strip('\r\n')
		except EOFError:
			return ''

def readi():
	return [int(t) for t in readline().split()]
(n, m) = readi()
s = readline()
summ = [[0] * n for i in range(6)]
k = 0
for i in itertools.permutations('abc', 3):
	t = ''.join(i)
	for i in range(n):
		if s[i] != t[i % 3]:
			summ[k][i] = 1
		if i > 0:
			summ[k][i] += summ[k][i - 1]
	k += 1
ans = [200000] * m
for i in range(m):
	(l, r) = readi()
	l -= 1
	r -= 1
	for j in range(6):
		if l - 1 >= 0:
			ans[i] = min(ans[i], summ[j][r] - summ[j][l - 1])
		else:
			ans[i] = min(ans[i], summ[j][r])
print(*ans, sep='\n')
if DEBUG == 1:
	data.close()


try:
	import sys
	from functools import lru_cache, cmp_to_key
	from heapq import merge, heapify, heappop, heappush
	from collections import defaultdict as dd, deque, Counter as C
	from itertools import combinations as comb, permutations as perm
	from bisect import bisect_left as bl, bisect_right as br, bisect, insort
	from time import perf_counter
	from fractions import Fraction
	import copy
	from copy import deepcopy
	import time
	starttime = time.time()
	mod = int(pow(10, 9) + 7)
	mod2 = 998244353

	def data():
		return sys.stdin.readline().strip()

	def out(*var, end='\n'):
		sys.stdout.write(' '.join(map(str, var)) + end)

	def L():
		return list(sp())

	def sl():
		return list(ssp())

	def sp():
		return map(int, data().split())

	def ssp():
		return map(str, data().split())

	def l1d(n, val=0):
		return [val for i in range(n)]

	def l2d(n, m, val=0):
		return [l1d(n, val) for j in range(m)]
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass
(n, m) = L()
s = input()
dp = [[[0, 0, 0] for i in range(3)] for j in range(n + 1)]
for i in range(1, n + 1):
	for j in range(3):
		for k in range(3):
			dp[i][j][k] = dp[i - 1][j][k] + 1 * int(ord(s[i - 1]) - ord('a') == j) * int((i - 1) % 3 == k)
for _ in range(m):
	(x, y) = L()
	ln = y - x + 1
	max_valid = 0
	z = [[0, 0, 0] for i in range(3)]
	for j in range(3):
		for k in range(3):
			z[j][k] = dp[y][j][k] - dp[x - 1][j][k]
	for i in range(3):
		for j in range(3):
			if i == j:
				continue
			for k in range(3):
				if k in [i, j]:
					continue
				curr_valid = z[0][i] + z[1][j] + z[2][k]
				max_valid = max(max_valid, curr_valid)
	print(ln - max_valid)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from itertools import permutations
from collections import *
from collections import deque
from operator import itemgetter, attrgetter
from decimal import *
import bisect
import math
import heapq as hq
MOD = 10 ** 9 + 7

def is_prime(n):
	if n == 2 or n == 3:
		return True
	if n < 2 or n % 2 == 0:
		return False
	if n < 9:
		return True
	if n % 3 == 0:
		return False
	r = int(n ** 0.5)
	f = 5
	while f <= r:
		if n % f == 0:
			return False
		if n % (f + 2) == 0:
			return False
		f += 6
	return True

def pow(a, b, m):
	ans = 1
	while b:
		if b & 1:
			ans = ans * a % m
		b //= 2
		a = a * a % m
	return ans

def ispalindrome(s):
	if s[:] == s[::-1]:
		return 1
	return 0
dp = []
limit = []
v = []

def dpdfs(u, t=-1):
	dp[0][u] = 0
	dp[1][u] = 0
	for i in v[u]:
		if i == t:
			continue
		if dp[1][i] == -1:
			dpdfs(i, u)
		dp[0][u] += max(abs(limit[0][u] - limit[1][i]) + dp[1][i], abs(limit[0][u] - limit[0][i]) + dp[0][i])
		dp[1][u] += max(abs(limit[1][u] - limit[1][i]) + dp[1][i], abs(limit[1][u] - limit[0][i]) + dp[0][i])
vis = []
f = 0

def dfs(i):
	vis[i] = 1
	act[i] = 1
	for j in v[i]:
		if act[j]:
			f = 1
			return -1
		if vis[j] == 0:
			if dfs(j) == -1:
				return -1
	act[i] = 0
	ans.append(i)
	return 0
from queue import PriorityQueue

def z_algorithm(s):
	res = [0] * len(s)
	res[0] = len(s)
	(i, j) = (1, 0)
	while i < len(s):
		while i + j < len(s) and s[j] == s[i + j]:
			j += 1
		res[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < len(s) and k + res[k] < j:
			res[i + k] = res[k]
			k += 1
		(i, j) = (i + k, j - k)
	return res

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a / gcd(a, b) * b

def gcdExtended(a, b):
	if a == 0:
		return (b, 0, 1)
	(gcd, x1, y1) = gcdExtended(b % a, a)
	x = y1 - b // a * x1
	y = x1
	return (gcd, x, y)
import re
(n, q) = map(int, input().split())
s = input()
temp = []
for p in permutations('abc'):
	temp.append(''.join(p))
prefix = [[0 for i in range(6)] for j in range(n + 1)]
for i in range(n):
	for j in range(6):
		prefix[i][j] = prefix[i - 1][j] + (temp[j][i % 3] != s[i])
for i in range(q):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	ans = math.inf
	for j in range(6):
		ans = min(ans, prefix[y][j] - prefix[x - 1][j])
	print(ans)


import sys
input = sys.stdin.readline
print = sys.stdout.write
(n, m) = map(int, input().split())
import math
s = input().rstrip()
c2 = math.ceil(len(s) / 3)
op1 = ('abc' * c2)[:len(s)]
op2 = ('acb' * c2)[:len(s)]
op3 = ('cab' * c2)[:len(s)]
op4 = ('cba' * c2)[:len(s)]
op5 = ('bac' * c2)[:len(s)]
op6 = ('bca' * c2)[:len(s)]
l = [op1, op2, op3, op4, op5, op6]
prefsumsmodels = []
for op in range(6):
	model = []
	for i in range(n):
		if l[op][i] != s[i]:
			model.append(1)
		else:
			model.append(0)
	prefsumsmodels.append(model)
prefsums = []
for model in prefsumsmodels:
	ps = [0]
	for i in range(n):
		ps.append(ps[i] + model[i])
	prefsums.append(ps)
for tc in range(m):
	(l, r) = map(int, input().split())
	ans = 10 ** 18
	for i in prefsums:
		changes = i[r] - i[l - 1]
		ans = min(ans, changes)
	print(str(ans) + '\n')


import sys
MOD = 3

def get_next(start, delta):
	return (start + delta) % MOD

def get_state(arr, start, dir):
	n = len(arr)
	state = []
	prev = 0
	cur = start
	for a in arr:
		state.append(prev + int(a != cur))
		prev = state[-1]
		cur = get_next(cur, dir)
	return state

def preprocess(arr):
	arr = [ord(a) - ord('a') for a in arr]
	states = {(start, dir): [0] + get_state(arr, start, dir) for start in range(MOD) for dir in [-1, 1]}
	return states

def solve(states, l, r):
	results = []
	for ((start, dir), state) in states.items():
		results.append(state[r] - state[l - 1])
	return min(results)

def main():
	outputs = []
	fin = sys.stdin
	(n, m) = map(int, fin.readline().split())
	arr = list(fin.readline().strip())
	states = preprocess(arr)
	requests = []
	for _ in range(m):
		(l, r) = map(int, fin.readline().split())
		outputs.append(solve(states, l, r))
	print('\n'.join(map(str, outputs)))
main()


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
s = input()
a = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
for i in range(6):
	a[i] = a[i] * (n // 3) + a[i] * (n % 3)
prefix = [[0 for i in range(n)] for j in range(6)]
for i in range(6):
	if a[i][0] != s[0]:
		prefix[i][0] = 1
for i in range(6):
	for j in range(1, n):
		if s[j] != a[i][j]:
			prefix[i][j] = prefix[i][j - 1] + 1
		else:
			prefix[i][j] = prefix[i][j - 1]
for i in range(m):
	(l, r) = map(int, input().split())
	minn = 10 ** 18
	for i in range(6):
		if l != 1:
			minn = min(minn, prefix[i][r - 1] - prefix[i][l - 2])
		else:
			minn = min(minn, prefix[i][r - 1])
	print(minn)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
s = input()
abc = []
for i in range(6):
	abc.append([0] * (n + 1))
words = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
tmps = [0] * 6
for i in range(n):
	for j in range(6):
		if words[j][i % 3] != s[i]:
			tmps[j] += 1
		abc[j][i + 1] = tmps[j]
for i in range(m):
	(l, r) = map(int, input().split())
	ans = r - l + 1
	for j in range(6):
		ans = min(ans, abc[j][r] - abc[j][l - 1])
	print(ans)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
s = input()
ss = ['abc', 'acb', 'cba', 'cab', 'bac', 'bca']
dp = []
for i in range(6):
	z = [0]
	x = ss[i] * (n // 3) + ss[i][:n % 3]
	for j in range(n):
		z.append(z[-1] + (s[j] != x[j]))
	dp.append(z)
for _ in range(m):
	(l, r) = map(int, input().split())
	ans = 1000000000.0
	for i in range(6):
		ans = min(ans, dp[i][r] - dp[i][l - 1])
	print(ans)


from collections import deque
import heapq
from math import sqrt
import operator
from operator import itemgetter
import sys
import copy
inf_var = 0
if inf_var == 1:
	inf = open('input.txt', 'r')
else:
	inf = sys.stdin
input = inf.readline

def read_one_int():
	return int(input().rstrip('\n'))

def read_one_float():
	return float(input().rstrip('\n'))

def read_list_of_ints():
	res = [int(val) for val in input().rstrip('\n').split(' ')]
	return res

def read_str():
	return input().rstrip()

def generate_strs(n, cur_str):
	diff_strs = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
	candidates = []
	for part_str in diff_strs:
		candidates.append(part_str * (n // 3))
		candidates[-1] += part_str[:n % 3]
	return candidates

def generate_part_sums(n, cur_str, cand_strs):
	part_sums = []
	for cand in cand_strs:
		part_sums.append([])
		part_sums[-1].append(int(cur_str[0] != cand[0]))
		for i in range(1, n):
			part_sums[-1].append(part_sums[-1][i - 1] + int(cur_str[i] != cand[i]))
	return part_sums

def main():
	(n, m) = read_list_of_ints()
	cur_str = read_str()
	inf = 10 ** 8
	cand_strs = generate_strs(n, cur_str)
	cand_part_sums = generate_part_sums(n, cur_str, cand_strs)
	for _ in range(m):
		(l, r) = read_list_of_ints()
		l -= 1
		r -= 1
		res = inf
		for part_sum in cand_part_sums:
			if l == 0:
				cur_res = part_sum[r]
			else:
				cur_res = part_sum[r] - part_sum[l - 1]
			res = min(res, cur_res)
		print(res)
main()