Chef and Piano Scales

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Recently, Chef got obsessed with piano. He is a just a rookie in this stuff and can not move his fingers from one key to other fast enough. He discovered that the best way to train finger speed is to play scales. There are different kinds of scales which are divided on the basis of their interval patterns. For instance, major scale is defined by pattern TTSTTTS, where ‘T’ stands for a whole tone whereas ‘S’ stands for a semitone. Two semitones make one tone. To understand how they are being played, please refer to the below image of piano’s octave – two consecutive keys differ by one semitone. If we start playing from first key (note C), then we’ll play all white keys in a row (notes CDEFGABC – as you can see C and D differ for a tone as in pattern, and E and F differ for a semitone). This pattern could be played some number of times (in cycle). Each time Chef takes some type of a scale and plays using some number of octaves. Sometimes Chef can make up some scales, so please don’t blame him if you find some scale that does not exist in real world. Formally, you have a set of 12 keys (i.e. one octave) and you have N such sets in a row. So in total, you have 12*N keys. You also have a pattern that consists of letters 'T' and 'S', where 'T' means move forward for two keys (from key x to key x + 2, and 'S' means move forward for one key (from key x to key x + 1). Now, you can start playing from any of the 12*N keys. In one play, you can repeat the pattern as many times as you want, but you cannot go outside the keyboard. Repeating pattern means that if, for example, you have pattern STTST, you can play STTST as well as STTSTSTTST, as well as STTSTSTTSTSTTST, as well as any number of repeating. For this pattern, if you choose to repeat it once, if you start at some key x, you'll press keys: x (letter 'S')> x + 1 (letter 'T')> x + 3 (letter 'T')> x + 5 (letter 'S') > x + 6 (letter 'T')> x + 8. Also 1 ≤ x, x + 8 ≤ 12*N so as to avoid going off the keyboard. You are asked to calculate number of different plays that can be performed. Two plays differ if and only if they start at different keys or patterns are repeated different number of times.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. First line of each test case contains scale’s pattern – string s consisting of letters ‘T’ and ‘S’ only. Second line contains one integer N – number of octaves he’ll be using.
Output
For each test case output a single number in a line corresponding to number of different scales he’ll play.
Constraints
 1 ≤ T ≤ 10^{5}
 1 ≤ S ≤ 100
 1 ≤ n ≤ 7
Subtasks
Subtask 1: T < 10 ^{4}, N = 1
Subtask 2: No additional constraints.
Example
Input: 2 TTTT 1 TTSTTTS 3 Output: 4 36
Explanation
Example case 1. In the first case there is only one octave and Chef can play scale (not in cycle each time) starting with notes C, C#, D, D#  four together.
Author:  witalij_hq 
Editorial  http://discuss.codechef.com/problems/PIANO1 
Tags  april15, loops, simple, witalij_hq 
Date Added:  24022015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 