Свободными вечерами Мистеру Б иногда нечем заняться, потому он ищет различные игры в интернете. И вот в один день он нашел интересную игру, в которой предлагалось сыграть против инопланетян.

Все символы в данной игре — строчные буквы английского алфавита. В данной игре участвуют два игрока: Мистер Б и его соперник.

Первоначально игрокам задана строка s из a первых символов английского алфавита в алфавитном порядке (при a = 5, например, строка s выглядит следующим образом: «abcde»).

Далее каждый игрок по очереди дописывает в конец строки s по несколько букв. Первым ходом ходит Мистер Б.

Мистер Б может добавить в конец строки ровно b произвольных букв. Его противник — ровно a букв.

Мистер Б быстро догадался, что его противник — никакой не инопланетянин, а компьютер, действующий по простой программе. Компьютер на очередном своем шаге рассматривает суффикс из последних a символов строки s и для своего хода выбирает строку t длины a такую, что все символы в t попарно различны, никакой из символов строки не встречается в рассматриваемом суффиксе, и из всех возможных вариантов t — лексикографически минимальный (при a = 4 и суффиксе «bfdd» компьютер выберет строку t, равную «aceg»). Далее выбранную строку t компьютер просто добавляет в конец строки s.

Мистеру Б уже надоело играть с компьютером, а потому его заинтересовал вопрос: какое минимальное количество различных символов могло быть в строке s на отрезке с символа номер l по символ номер r, включительно. Символы строки s нумеруется слева направо, начиная с 1.