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