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