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