Duff в ярости на своих друзей. От злости она просит Malek'а отнимать конфеты у её друзей безо всякого повода!
У неё n друзей. Её i-ого друга зовут si (их имена не обязательно уникальны). Она попросить Malek'а забрать конфеты у её друзей q раз. Она в ярости, но всё же она действует по определённым правилам. Когда она хочет попросить Malek'а забрать конфету у одного из её друзей, имеющего номер k, она выбирает два числа, l и r и говорит Malek'у взять ровно 
конфет у друга, где occur(t, s) — это число вхождений строки t в строку s.
Malek не может посчитать, сколько конфет надо забрать в каждом из запросов Duff. Поэтому он просит вас о помощи. Пожалуйста, скажите ему, сколько конфет взять в каждом запросе.
Выходные данные
Выведите ответ на каждый запрос в одной строке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 5
a
ab
abab
ababab
b
1 5 4
3 5 4
1 5 2
1 5 3
1 4 1
|
12
6
3
7
1
|