Instant messaging system
Rabbit Stew to communicate to rabbit Roger uses “complicated” encoding system – so nobody can guess.
All messages contain lowercase letters a..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 g is encoded as ghg, z – zaz, a – aba. Hence, message hello converts into hihefelmllmlopo.
For encoding initial message has been converted k times and Stew is interested how many distinct letters are necessary to type part of encoded message from a-th to b-th letter inclusively (enumerating from 0).
Input
The first line at input contains single integer T (1 ≤ T ≤ 1000), number of tests. Each test consists of 2 lines. The first line contains non empty string of letters – initial message, that consist of not more than 100 lowercase letters. The second line contains three integers, separated by spaces: k, a, b – number of algorithm iterations, start and end of the interval correspondingly (0 ≤ k ≤ 15, a ≤ b, 0 ≤ a, b < length of the encoded message).
Output
For every test you need to output answer into a separate line.