PROG0005 - Letter game

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

Bij een eenvoudig letterspelletje wordt bij elke beurt in een gegeven string — die enkel bestaat uit de letters a en b — elk voorkomen van de letter b vervangen door de letters ab, en elk voorkomen van de letter a vervangen door de letter b.

Stel dat we bijvoorbeeld beginnen met "abba". Na de eerste beurt is deze string gewijzigd in "bababb", door de a's te vervangen door de letter b en de b's te vervangen door ab. Op deze manier wordt de string na verloop van tijd wel heel erg lang. Vraag is hoe lang de string wordt nadat n vervangingen zijn doorgevoerd?

Invoer

De invoer bestaan uit $t$ testgevallen ($t \leq 100$). De eerste regel van de invoer bevat een natuurlijk getal $t$. Daarna volgen $t$ regels die de verschillende testgevallen omschrijven. Elk geval wordt omschreven door een string $s$ en een natuurlijk getal $n$ ($0 < n \leq 50$). Je mag ervan uitgaan dat $s$ enkel bestaat uit de letters a en b, en niet meer dan 100 letters telt.

Uitvoer

Schrijf voor elk testgeval de lengte van de gegeven string na $n$ vervangingen uit op een afzonderlijke regel.

Voorbeeld

Invoer:

3
abba 1
abba 2
abbaabbababaabba 50

Uitvoer:

6
10
426530329384

Added by:Peter Dawyndt
Date:2011-07-09
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:PY_NBC
Resource:None

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.