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