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 T-T-S-T-T-T-S, 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 C-D-E-F-G-A-B-C – 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 ≤ 105
- 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.

Difficulty: MEDIUM_HARD
Tags: Complete search
Skill types: Complete search

Starter code:

Solutions:
for t in range(int(input())):
	s = input()
	n = int(input())
	l = len(s)
	c = 0
	for i in range(l):
		if s[i] == 'T':
			c += 2
		else:
			c += 1
	p = 0
	r = 12 * n
	while r - c > 0:
		r -= c
		p += r
	print(p)


for _ in range(0, int(input())):
	s = str(input())
	ct = 2 * s.count('T')
	cs = s.count('S')
	x = int(input())
	s = 12 * x
	c = ct + cs
	z = c
	res = 0
	while s >= c:
		res += s - c
		c += z
	print(res)


def solution():
	s = input()
	n = int(input())
	length = 0
	for (i, c) in enumerate(s):
		if c == 'T':
			length += 2
		else:
			length += 1
	count = 0
	for i in range(length, 12 * n, length):
		count += 12 * n - i
	print(count)
T = int(input())
while T > 0:
	T = T - 1
	solution()


t = int(input())
while t:
	s = input()
	n = int(input())
	mSum = 0
	for i in range(len(s)):
		if s[i] == 'T':
			mSum += 2
		else:
			mSum += 1
	count = 0
	for i in range(1, 12 * n + 1):
		if mSum + i > 12 * n:
			break
		count += (12 * n - i) // mSum
	print(count)
	t -= 1


t = int(input())
for _ in range(t):
	s = str(input())
	n = int(input())
	keys = 12 * n
	forward = s.count('T') * 2 + s.count('S')
	plays = 0
	for i in range(keys):
		plays += (keys - i - 1) // forward
	print(plays)


for _ in range(int(input())):
	St = input()
	St_count = St.count('S') + 2 * St.count('T')
	n = 12 * int(input())
	sum_ = n * (n // St_count)
	for i in range(n // St_count):
		sum_ -= (i + 1) * St_count
	print(sum_)


def soln(n, s):
	if len(s) > n * 12:
		return 0
	scale_len = 0
	for i in s:
		if i == 'T':
			scale_len += 2
		else:
			scale_len += 1
	keys = n * 12
	mul = keys // scale_len
	res = (keys - scale_len) * mul
	for i in range(mul):
		res -= i * scale_len
	return res
for _ in range(int(input())):
	s = input()
	n = int(input())
	print(soln(n, s))


for _ in range(int(input())):
	strng = str(input())
	n = int(input())
	ln = 12 * n
	t_count = strng.count('T')
	s_count = strng.count('S')
	dd = 2 * t_count + s_count
	ans = 0
	for i in range(dd, ln, dd):
		ans += ln - i
	print(ans)


t = int(input())
for t0 in range(t):
	s = input()
	n = int(input())
	n1 = 0
	for i in s:
		if i == 'T':
			n1 += 2
		else:
			n1 += 1
	d = n * 12
	x = 0
	i = 1
	while i * n1 < d:
		x += d - i * n1
		i += 1
	print(x)


T = int(input())
for t in range(T):
	s = input()
	n = int(input())
	x = sum(({'S': 1, 'T': 2}[i] for i in s))
	k = 12 * n // x
	m = 12 * n * k - k * (k + 1) * x // 2
	print(m)


trendy = int(input())
for _ in range(trendy):
	sammy = input()
	n = int(input()) * 12
	k = sum((1 if i == 'S' else 2 for i in sammy))
	ways = 0
	for i in range(n):
		ways += (n - i - 1) // k
	print(ways)


def opts(pl, ks):
	if pl > ks:
		return 0
	s = ks % pl
	e = ks - pl
	n = (e - s) // pl + 1
	return (s + e) * n // 2
for _ in range(int(input())):
	pl = sum((2 if x == 'T' else 1 for x in input()))
	ks = 12 * int(input())
	print(opts(pl, ks))


t = int(input())
for _ in range(t):
	s = input()
	n = int(input()) * 12
	k = sum((1 if i == 'S' else 2 for i in s))
	arr = [0] * n
	for i in range(n):
		arr[i] = (n - i - 1) // k
	print(sum(arr))


from collections import Counter

def solve():
	dct = Counter(s)
	total_steps = 2 * dct.get('T', 0) + dct.get('S', 0)
	d = total_steps
	count = 0
	for i in range(d, 12 * n, total_steps):
		count += 12 * n - i
	print(count)
t = int(input())
for _ in range(t):
	s = input()
	count = 0
	n = int(input())
	solve()


t = int(input())
while t != 0:
	n = input()
	o = int(input())
	c = 0
	ans = 0
	for i in n:
		if i == 'T':
			c += 2
		else:
			c += 1
	x = 12 * o
	i = 1
	while True:
		if i * c + 1 > x:
			break
		ans += x - c * i
		i += 1
	print(ans)
	t -= 1


import os.path
from math import gcd, floor, ceil, log2
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
for _ in range(int(input())):
	s = input()
	n = inp()
	l = s.count('T') * 2 + s.count('S')
	res = 0
	i = l
	while i <= 12 * n:
		res += 12 * n - i
		i += l
	pr(res)


t = int(input())
for _ in range(t):
	s = input()
	n = int(input())
	pc = n * 12
	cnt = s.count('S') + s.count('T') * 2
	nr = pc // cnt
	sm = (pc - cnt) * nr
	sm -= nr * (nr - 1) // 2 * cnt
	print(sm)


t = int(input())
for i in range(t):
	s = input().rstrip()
	n = int(input())
	count = 0
	for k in s:
		if k == 'T':
			count += 2
		elif k == 'S':
			count += 1
	d = count
	ans = 0
	while d < 12 * n:
		ans += 12 * n - d
		d = d + count
	print(ans)


def substring(total, part):
	return max(total - part + 1, 0)

def count_part(string):
	count = 0
	for x in string:
		if x == 'S':
			count += 1
		else:
			count += 2
	return count + 1

def total_ans(start, total):
	count = 0
	value = start
	while True:
		if substring(total, value) > 0:
			count += substring(total, value)
			value += start - 1
		else:
			break
	print(count)
for _ in range(int(input())):
	string = str(input())
	total = int(input())
	total = 12 * total
	start = count_part(string)
	total_ans(start, total)


t = int(input())
for i in range(t):
	C = [ord(x) - ord('R') for x in list(input())]
	N = int(input())
	L = sum(C)
	r = 1
	c = 0
	while r * L < N * 12:
		c += N * 12 - r * L
		r += 1
	print(c)


for _ in range(int(input())):
	s = input()
	n = int(input())
	lt = 0
	for m in s:
		if m == 'T':
			lt += 2
		else:
			lt += 1
	ans = 0
	i = 1
	while 12 * n > i * lt:
		ans += 12 * n - i * lt
		i += 1
	print(ans)


for _ in range(int(input())):
	S = input()
	n = int(input())
	keys = 12 * n
	t = S.count('T')
	pl = 2 * t + len(S) - t
	p = 1
	res = 0
	while p * pl < keys:
		res += keys - p * pl
		p += 1
	print(res)


mod = 1000000007
read_int = lambda : int(input().strip())
read_str = lambda : input().strip()
read_str_arr = lambda : input().strip().split()
read_int_arr = lambda : [int(x) for x in input().strip().split()]

def solve():
	s = read_str()
	n = read_int()
	(nt, ns) = (0, 0)
	for e in s:
		if e == 'T':
			nt += 1
		else:
			ns += 1
	ans = 0
	for i in range(12 * n):
		p = (12 * n - i - 1) // (2 * nt + ns)
		if p == 0:
			break
		ans += p
	print(ans)
for _ in range(int(input())):
	solve()


t = int(input())
for _ in range(t):
	s = input()
	n = int(input())
	k = 0
	for c in s:
		if c == 'T':
			k += 2
		else:
			k += 1
	cnt = 0
	for i in range(1, 12 * n // k + 1):
		last_start = 12 * n - i * k - 1
		cnt += last_start + 1
	print(cnt)


t = int(input())
while t > 0:
	s = input()
	n = int(input())
	key = n * 12
	count = 0
	for i in s:
		if i == 'T':
			count += 2
		else:
			count += 1
	n1 = 1
	scales = 0
	while n1 * count < key:
		scales += key - n1 * count
		n1 += 1
	print(scales)
	t -= 1


for tc in range(int(input())):
	x = str(input())
	n = int(input())
	keyboardlen = 12 * n
	a = list(x)
	r = a.count('T') * 2 + a.count('S')
	l = keyboardlen // r
	ans = keyboardlen * l - l * r * (l + 1) // 2
	print(ans)


t = int(input())
for _ in range(t):
	s = input()
	n = int(input())
	n *= 12
	cnt = s.count('S') + s.count('T') * 2
	sm = (n - cnt) * (n // cnt)
	for i in range(n // cnt):
		sm -= i * cnt
	print(sm)


import math

def solve(l, n):
	ans = 0
	k = 12 * n
	for i in range(l, k, l):
		ans += 12 * n - i
	return ans
t = int(input())
for r in range(1, t + 1):
	s = input()
	l = 0
	for c in s:
		if c == 'T':
			l += 2
		elif c == 'S':
			l += 1
	n = int(input())
	result = solve(l, n)
	print(str(result))


KEYS = 12
T = int(input())
for _ in range(T):
	scale = list(input())
	n = int(input())
	length = 0
	for move in scale:
		if move == 'S':
			length += 1
		elif move == 'T':
			length += 2
	num = 0
	k = 1
	while k * length < n * KEYS:
		num += n * KEYS - k * length
		k += 1
	print(num)


t = int(input())
while t:
	t -= 1
	s = input()
	n = int(input())
	s1 = 0
	for i in s:
		if i == 'T':
			s1 += 2
		else:
			s1 += 1
	(f, c, t1, t2) = (0, 0, 12 * n, 0)
	while f < t1:
		t2 = f
		while t2 + s1 < t1:
			t2 += s1
			c += 1
		f += 1
	print(c)


t = int(input())
out = []
for i in range(t):
	s = input()
	n = int(input())
	S = 0
	for j in s:
		if j == 'T':
			S += 2
		else:
			S += 1
	N = 12 * n
	Out = 0
	for j in range(N - S):
		Out += (N - 1 - j) // S
	out.append(Out)
for i in out:
	print(i)


for i in range(int(input())):
	s = input()
	n = int(input())
	x = 0
	for j in range(len(s)):
		if s[j] == 'T':
			x = x + 2
		elif s[j] == 'S':
			x = x + 1
	ans = 0
	keys = n * 12
	d = x
	while x <= keys:
		ans += keys - x
		x += d
	print(ans)


num = int(input())
while num:
	p = list(input())
	n = int(input())
	n = n * 12
	t = 0
	s = 0
	for i in p:
		if i == 'T':
			t += 1
		else:
			s += 1
	n2 = 2 * t + s
	if n2 + 1 > n:
		print(0)
	elif n2 + 1 == n:
		print(1)
	else:
		n = n - 1
		c = n // n2
		count = 0
		while c != 0:
			count += n - c * n2 + 1
			c -= 1
		print(count)
	num -= 1


T = int(input())
for i in range(T):
	C = [ord(x) - ord('R') for x in list(input())]
	N = int(input())
	L = sum(C)
	repeat = 1
	count = 0
	while repeat * L < N * 12:
		count += N * 12 - repeat * L
		repeat += 1
	print(count)


steps = {'T': 2, 'S': 1}
octave = 12

def length(phrase):
	return sum([steps[s] for s in phrase])

def results(keys, l):
	return keys - l
for t in range(int(input())):
	s = str(input())
	n = int(input())
	ans = 0
	repeat = 1
	number_of_keys = octave * n
	r = results(number_of_keys, length(s * repeat))
	while r >= 0:
		ans += r
		repeat += 1
		r = results(number_of_keys, length(s * repeat))
	print(ans)


t = int(input())
while t > 0:
	pattern = input()
	Ts = pattern.count('T')
	Ss = pattern.count('S')
	pl = 2 * Ts + Ss
	octave = int(input())
	keys = 12 * octave
	pn = 1
	scales = 0
	while pn * pl < keys:
		scales += keys - pn * pl
		pn += 1
	print(scales)
	t -= 1


t = int(input())
for test in range(t):
	num = input()
	n = int(input())
	x = 0
	for i in num:
		if i == 'T':
			x += 2
		else:
			x += 1
	ans = 0
	keys = n * 12
	d = x
	while x <= keys:
		ans += keys - x
		x += d
	print(ans)


for _ in range(int(input())):
	s = input()
	length = 0
	for i in s:
		if i == 'T':
			length += 2
		elif i == 'S':
			length += 1
	n = int(input()) * 12
	num = 0
	m = 1
	while m * length <= n:
		a = n - m * length
		num += a
		m += 1
	print(num)


def main():
	T = int(input())
	output = list()
	oct = '1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6 6.5'
	octa = oct.split()
	octave = list()
	for o in octa:
		octave.append(float(o))
	for testcase in range(0, T):
		set = input()
		buildset = ''
		N = int(input())
		counter = 0
		singlePatternsize = 0.0
		for character in set:
			if character == 'T':
				singlePatternsize = singlePatternsize + 1.0
			else:
				singlePatternsize = singlePatternsize + 0.5
		flag = 1
		K = 0.0
		while flag != counter:
			flag = counter
			K = K + singlePatternsize
			for repeats in range(0, N):
				for key in octave:
					FinalKey = key + 6.0 * repeats + K
					Comparator = 6.5 + (N - 1) * 6.0
					if FinalKey <= 6.5 + (N - 1) * 6.0:
						counter += 1
		output.append(counter)
	for x in output:
		print(x)
main()


for _ in range(int(input())):
	pattern = input()
	N = int(input())
	length = 12 * N
	keys_in_pattern = 0
	for i in range(len(pattern)):
		if pattern[i] == 'S':
			keys_in_pattern += 1
		else:
			keys_in_pattern += 2
	repeats = length // keys_in_pattern
	ans = 0
	for i in range(1, repeats + 1):
		ans += length - i * keys_in_pattern
	print(ans)


for _ in range(int(input())):
	p = sum([{'T': 2, 'S': 1}[i] for i in input()])
	o = int(input()) * 12
	x = o // p
	print(o * x - p * sum(range(x + 1)))


T = int(input())
for _ in range(T):
	L = list(input())
	n = int(input())
	n *= 12
	x = 0
	for i in range(len(L)):
		if L[i] == 'T':
			x += 2
		else:
			x += 1
	ans = 0
	y = x
	while x + 1 <= n:
		a = n - x
		ans += a
		x += y
	print(ans)