NSUJ02D - String Game

Natasha is playing an innocent game since she is very very bored. She initially wrote a string that only contains 'a' or 'b'. After in each turn, that she replaces all the 'b' with 'ab' and all the 'a' with 'b'.

For example if she starts with "abba". Next time she'd write "bababb", by replacing 'a's with 'b' and 'b's with 'ab'. But in that way, after a while the string gets really really big. Now she wonders if she does this work for n times, what would be the length of the string?

Input

First line contains number of test cases - t. After that t lines will follow, each will have an initial string and n. You can assume the given string won't have more than 100 characters and n will be a positive integer not more than 50.

Output

For each case output the length of the string after n turns.

Example

Input:
3
abba 1
abba 2
abbaabbababaabba 50 Output: 6
10
426530329384

Added by:Iqram Mahmud
Date:2011-07-03
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own

hide comments
2018-05-27 14:08:49
Useful tutorial problem, beginners can pick up a thing or two here.
2013-12-29 12:24:04 Nitto Janitto
Sample Input:
5
abba 1
abba 2
abba 3
abbaabbababaabba 50
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb 50
Sample Output:
6
10
16
426530329384
3295128009900
2011-07-19 09:45:40 Noszály Csaba
Ben: None.

Last edit: 2011-07-19 09:45:57
2011-07-10 18:12:39 Ben
Is there any other assumptions we may make about the inputs not listed here?
2011-07-09 21:22:16 Ben
I have submitted a solution which seems to emit correct output, but I get a "Wrong Answer" result from the judge.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.