Строка t называется красивой, если строка «2017» встречается в t в качестве подпоследовательности, а строка «2016» не встречается в t в качестве подпоследовательности. Например, строки «203434107» и «9220617» являются красивыми, а строки «20016», «1234» и «20167» не являются красивыми.
Уродством строки называется минимальное количество символов, которые надо удалить, чтобы получить красивую строку. Если получить красивую строку удаляя символы невозможно, то её уродство равняется - 1.
У Лимака есть строка s длины n, символы которой пронумерованы от 1 до n. Также у него есть q запросов. В i-м запросе выведите уродство подстроки (непрерывной подпоследовательности) s начинающейся с позиции номер ai и заканчивающейся в позиции номер bi (включительно).
Выходные данные
Для каждого запроса выведите уродство соответствующей подстроки.
Примечание
Рассмотрим первый пример. Далее запись ugliness(t) означает уродство строки t.
- В первом запросе ugliness(«20166766») = 4, потому что потребуется удалить все четыре шестёрки.
- Во втором запросе ugliness(«2016676») = 3, поскольку потребуется удалить все три шестёрки.
- В третьем запросе ugliness(«0166766») = - 1, так как нельзя сделать данную строку красивый удалением какого-либо числа символов.
Во втором примере:
- Во втором запросе ugliness(«01201666209167») = 2. Оптимальным ответом будет удалить первую цифру «2» и последнюю цифру «6», что даст строку «010166620917», которая является красивой.
- В третьем запросе ugliness(«016662091670») = 1. Оптимальным ответом является удалить последнюю цифр «6», что даст красивую строку «01666209170».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8 3
20166766
1 8
1 7
2 8
|
4
3
-1
|
|
2
|
15 5
012016662091670
3 4
1 14
4 15
1 13
10 15
|
-1
2
1
-1
-1
|
|
3
|
4 2
1234
2 4
1 2
|
-1
-1
|