Система миттєвого обміну повідомленнями#3212
Кролик Стю використовує «складну» систему кодування для спілкування з кроликом Роджером, щоб ніхто не зміг зрозуміти їхні повідомлення.
Усі повідомлення складаються лише з малих латинських літер: a..z. Для кодування використовується такий алгоритм: на одному кроці кодування кожна літера в оригінальному повідомленні замінюється на три літери, де перша й третя — це та ж сама літера, а друга — наступна літера за абеткою (після останньої літери знову йде перша). Наприклад, літера g перетворюється на ghg, літера z — на zaz, а літера a — на aba. Таким чином, повідомлення hello перетворюється на hihefelmllmlopo.
Процес кодування застосовується до початкового повідомлення разів. Стю цікавиться, скільки різних літер потрібно, щоб записати фрагмент закодованого повідомлення з -ї до -ї літери (включно, рахуючи від нуля).
Перший рядок містить одне ціле число (1 \leq T \leq 1000) — кількість тестів. Кожен тест складається з двох рядків. Перший рядок містить початковий непорожній рядок, що складається не більш ніж зі малих латинських літер. Другий рядок містить три цілі числа, розділені пробілами: , та — кількість разів застосування алгоритму, початок і кінець фрагмента відповідно (0 \leq k \leq 15, a \leq b, 0 \leq a, b < довжина закодованого повідомлення).
Для кожного тесту виведіть відповідь в окремому рядку.
Приклад 1