VPL2_AC - Primos Quest

Primo is playing Guitar Hero, but he has been playing it for quite long, and his hand is a little tired. He knows that for every change between colors his energy goes down. The colors of the guitar are ordered like this: Green, Red, Yellow, Blue and Orange. The energy to change from playing a color A, to a color B, is the absolute difference of the distance between them, by example, changing from Red to Yellow, costs 1 unit of energy, and changing from Blue to Green costs 3 units of energy. Primo knows that he has exactly C units of energy left, and he also know the colors of the notes from a random song. Help him find out the maximum number of notes in a row that he can play on this song.

Input

The first line contains an integer T, which specifies the number of test cases. Then, will follow the descriptions of T test cases.

For each test case you will have a single line containing an integer C, representing the energy left of Primo, and a string S, representing the colors and the order of the notes from the song. Each character in S will be ’G’ for Green, ’R’ for Red, ’Y’ for Yellow, ’B’ for Blue or ’O’ for Orange.

Output

For each input case you must print Scenario #i: where i is the number of the test case (starting at one), and then the answer to the problem.

Sample

Input
3
0 OORRBYYYGG
1 RRORGRRRBOY
3 RRRORORRRR

Output
Scenario #1: 3
Scenario #2: 4
Scenario #3: 5

Constraints

Constraints - 40%

1 ≤ T ≤ 100

0 ≤ C, |S| ≤ 1000

Constraints - 60%

1 ≤ T ≤ 100

0 ≤ C, |S| ≤ 1000000


Added by:Venezuelan Programming League
Date:2013-06-22
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2013-06-29 15:15:08 Shubham Sharma
Please explain the test cases!!!
2013-06-29 15:15:08 Anuj_LuckFove!
AC :P

Last edit: 2013-06-24 17:24:03
2013-06-29 15:15:08 Kevin Sebastian
@Xsquare the ans is 4 as crossing from G to R costs 1 extra unit of energy
2013-06-29 15:15:08 shiv prasad chabarval
please explain test cases.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.