Instant messaging system#3212
Rabbit Stew uses a "complicated" encoding system to communicate with rabbit Roger so that nobody can understand their messages.
All messages consist only of lowercase Latin letters: a..z. The following algorithm is used for encoding: One step of encoding replaces each letter in the original message with three letters, where the first and third letters are the same as the original letter, and the second letter is the next letter in the alphabet (after the last letter, the first letter starts again). For example, the letter g becomes ghg, the letter z becomes zaz, and the letter a becomes aba. Thus, the message hello is converted to hihefelmllmlopo.
The encoding process is applied to the original message times. Stew is interested in how many distinct letters are required to write a segment of the encoded message from the -th to the -th letter (inclusive, counting from zero).
The first line contains a single integer (1 \leq T \leq 1000), the number of tests. Each test consists of two lines. The first line contains the initial non-empty string, consisting of at most lowercase Latin letters. The second line contains three integers separated by spaces: , , and — the number of times the algorithm is applied, and the segment's start and end positions, respectively (0 \leq k \leq 15, a \leq b, 0 \leq a, b < length of the encoded message).
For each test, output the answer on a separate line.
Example 1