Luis is seeing his son playing, he ask him gently in what the game consists, the boy replies “Its like this, you have a big number, a bound and a “mod” (the remainder of a division between a number and “mod”), the goal of the game is to discover the maximum sub-number you can create following this rules:”

• The sequence must not decrease lower from the first digit taken.

• The sequence chosen must not reach the bound. By example, if the first digit is 'd' and a bound 'k', the range you can take is between [d,min(d+k,9)]

• You can start from any digit of a number.

• For any given start point, you should look for the sub-numbers making the maximum sum applied to the mod operation.

Luis, astonished by the explanation, request his son to give him and example, the boy then continues: “Suppose a number like this: 56789, a bound of 2, and a mod 10. you start with 5, being the bound of 2, this mean you can take up to the digit 7 (this means that you can always collect as many fives, sixes and sevens following the rules explained). The sub-number formed is of “5+6+7”, following the rules, we will have all others sub-numbers: “6+7+8” “7+8+9” “8+9” and “9”, after applying the operation, you will find that the maximum remainder of the sub-number's sum will be of “9”, made by the sub-number “9”.

Luis is a former programmer now and he does not have the same ability he had years ago, please, help him in his task following the game previously defined.

INPUT:

The first line of input will contain an integer T denoting the T test cases, then, T cases will follow. Each of the following cases will contain a line with an integer L, a big number N in the range [10^(L-1),(10^L)-1], an integer K denoting the bound and the M that will be the mod of the whole operation.

OUTPUT:

Output the string “Scenario #i: “ where i is the test case you are analyzing followed by the maximum sum of the sub-sequence that can be formed.

SAMPLE DATA:

CONSTRAINTS:

1<=L<=100000

10^(L-1)<=N<(10^L)-1

1<=K<=8

1<=M<=45