Let us play a simple letter game in which the letters in a given string - consisting only of the letters a and b - are replaced at every turn. Every occurrence of the letter b is replaced by the letters ab, and every occurrence of the letter a is replaced by the letter b.

Suppose we start with "abba". After the first turn, this string has changed to "bababb", by replacing the a's by the letter b and by replacing the b's with ab. In this way, the string eventually becomes very long. How long is the string after n substitutions?

Input

The input consists of $$t$$ test cases ($$t \leq 100$$). The first line of the input contains a natural number $$t$$. This is followed by $$t$$ lines that describe the various test cases. Each case is defined by a string $$s$$ and a natural number $$n$$ ($$0 < n \leq 50$$). You may assume that $$s$$ consists only of the letters a and b, and counts no more than 100 characters .

Output

Write the length of the given string after $$n$$ replacements on a separate line for each test case.

Example

Input:

3
abba 1
abba 2
abbaabbababaabba 50

Output:

6
10
426530329384