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