Однажды Петя в очередной раз написал грустную песню про любовь и поспешил показать ее Васе. Песня представляет собой строку из маленьких букв английского алфавита. У Васи сразу возникло \(q\) вопросов про эту песню. Каждый вопрос представляет собой некоторый отрезок песни с позиции \(l\) до позиции \(r\). Вася рассматривает подстроку, образованную символами на этом отрезке, а затем повторяет каждую букву в этой подстроке \(k\) раз, где \(k\) — порядковый номер буквы в алфавите. Например, если Вася выбрал подстроку «abbcb», то он повторит букву «a» один раз, каждую из букв «b» — по два раза, букву «c» — три раза, и полученная строка будет равна «abbbbcccbb», ее длина равна \(10\). Вася интересуется именно длиной полученной строки.
Помогите Пете ответить Васе на его вопросы, а именно, для каждого из заданных вопросов определите длину строки, которую выпишет Вася.
Выходные данные
Выведите \(q\) строк — для каждого вопроса выведите длину строки, которую выпишет Вася.
Примечание
В первом примере Васю интересуют три вопроса. В первом вопросе Вася рассматривает подстроку «aba», которая превратится в «abba», а значит, ответ на этот вопрос равен \(4\). Во втором вопросе Вася рассматривает подстроку «baca», которая превратится в «bbaccca», а значит, ответ на этот вопрос будет равен \(7\). В третьем вопросе Вася рассматривает всю строку «abacaba», которая превратится в «abbacccabba» — строку длины \(11\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 3
abacaba
1 3
2 5
1 7
|
4
7
11
|
|
2
|
7 4
abbabaa
1 3
5 7
6 6
2 4
|
5
4
1
5
|
|
3
|
13 7
sonoshikumiwo
1 5
2 10
7 7
1 13
4 8
2 5
3 9
|
82
125
9
191
62
63
97
|