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