Rabbit Stew to communicate to rabbit Roger uses “complicated” encoding system -- so nobody can guess. All messages contain lowercase letters \textbf{a}..\textbf{z} only. The following algorithm is used for encoding: One step of encoding is to take original message and replace each letter with 3 letters, where the first and third are same as original letter, the second is a letter which follows original in the alphabet (after last letter in the alphabet first letter comes again). For example, letter \textbf{g} is encoded as \textbf{ghg}, \textbf{z} -- \textbf{zaz}, \textbf{a} -- \textbf{aba}. Hence, message \textbf{hello} converts into \textbf{hihefelmllmlopo}. For encoding initial message has been converted \textbf{k} times and Stew is interested how many distinct letters are necessary to type part of encoded message from \textbf{a}-th to \textbf{b}-th letter inclusively (enumerating from \textbf{0}). \InputFile The first line at input contains single integer \textbf{T} (\textbf{1} ≤ \textbf{T} ≤ \textbf{1000}), number of tests. Each test consists of \textbf{2} lines. The first line contains non empty string of letters -- initial message, that consist of not more than \textbf{100} lowercase letters. The second line contains three integers, separated by spaces: \textbf{k}, \textbf{a}, \textbf{b} -- number of algorithm iterations, start and end of the interval correspondingly (\textbf{0} ≤ \textbf{k} ≤ \textbf{15}, \textbf{a} ≤ \textbf{b}, \textbf{0} ≤ \textbf{a}, \textbf{b} < \textbf{length of the encoded message}). \OutputFile For every test you need to output answer into a separate line.