Raju and his girlfriend

3

2 votes
Problem

Raju has a very pretty girlfriend. He chats with her all day and night through his phone. His phone lacks a QWERTY keypad, instead it has a T9 keypad.

This takes a lot of time to type a message in his phone and he often fears that his girlfriend might get angry if he doesn't reply on time. So he sets a time limit to type a message. He will send the message after time Z even if the message is not complete.

Also he is very slow in typing and can type only with his right thumb. He takes X time units to shift his thumb from one key to another and Y time units to press any key for one time.

Given the message he wants to send, calculate the part of the message he is able to send in Z time units. Input

The first line contains an integer T, the number of testcases. The first of each testcase includes three numbers X,Y and Z. The second line of each testcase includes a message M.

Output

Output should contain T lines, each line comprising of the part of the message actually sent for each testcase.

NOTE 1: Assume his thumb is at KEY1 at time 0. 
NOTE 2: KEY0 contains characters '_' and '0' in order. '_'(underscore) is used instead of a white space. 
NOTE 3: KEY1 contains characters '.'(dot), ','(comma), '?', '!' and '1' in order.
NOTE 4: All keys comprise of lower case English alphabets only.

Constraints

1<=T<=1000
1<=X,Y<=10
X,Y<=Z<=100
2<=M<=10
Time Limit: 3
Memory Limit: 256
Source Limit:
Explanation

Example case 1. He takes 1 time unit to move his thumb from KEY1 to KEY4. Then he takes 3 time units to press KEY4 three times. Again he moves his finger to KEY5 which took him 1 more time unit. He presses KEY5 two times losing 3 time units. He takes 1 time unit to move on to KEY8 and finally pressing it two times again losing 2 more time units. Total time span in this process = 1+3+1+3+1+2 = 11 time units.

Editor Image

?