Description

Nothing to say, just solve it...

**Note: ** ω means omega — The first transfinite ordinal, the smallest ordinal greater than all the positive integers.

Middle-growing hierarchy has following rules:

m ( 0 , n ) = n + 1

m ( α + 1 , n ) = m ( α , m ( α , n ) )

m ( α , n ) = m ( α [ n ] , n )

Although it is not clarified in the original definition, ω denotes a countable ordinal equipped with a fixed system of fundamental sequences of limit ordinals up to ω , and n denotes a natural number.

Input

The first line contains the number of test cases t (1<=t<=500) The description of the test cases follows.

The only line of each test case contains two integers α , n (1<=n<=100), (1<= α <=100)

α also denotes as ω (i can be used as w)

Output

For each test case, output answer

Examples

Example 1

Input

5

1 1

2 2

7 2

w 3

0 0

Output

3

6

130

11

1

Source: MGH