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

Description

There is a Hydra, that you need to slay: it has n types of heads, numbered from 1 to n («lower» till «higher»). You can strike one head and cut it, but every head produces other heads. Your goal is to slay the hydra with minimum amount of strikes. Hydra is killed, when after cutting the last head, other won't appear.

Input

First string contains n — nuuber of head types (1 ≤ n ≤ 2000). The second string contains n elements: a_1 ... a_n (0 ≤ a_i ≤ 10^9) — starting quantity of every heads. Then comes n string, containing n nums (matrix b).

Output

Minimum amount of strikes to slay the Hydra. Write -1 if it is impossible

Examples

Example 1

Input:

• 3
• 1 0 0
• 0 1 2
• 0 0 0
• 0 0 0

Output:

• 4

Example 2

Input:

• 5
• 1 1 1 1 1
• 0 1 0 0 0
• 0 0 1 0 0
• 0 0 0 1 0
• 0 0 0 0 1
• 0 0 0 0 0

Output:

• 31

Example 3:

Input:

• 1
• 1
• 1

Output:

• -1

Description

Tetration is a binary operator, defined as ʸx=xˣ(y times)ˣ. In other words, tetration is repeated exponentiation. In arrow notation it is defined as x^^y. Your goal is to count x^^y.

• Input file contains two numbers x (1<=x<=1234), y (0<=y<=2)
• Output contains one number y — answer.

Input, output

Example 1

Input

2 2

Output

4

Example 2

Input

5 0

Output

1

Example 3

Input

6 2

Output

46656

Soucre: Tetration

Stas plays a very hard game, called I wanna be the professor. It is similar to I wanna be the Guy, but it is also needed to solve mathematical problems to advance. Once he reached the boss, and now he must calculate the Fast-growing hierarchy to beat the boss.

INPUT

n, a

OUTPUT

Print f — the answer

Example

INPUT

0 1

OUTPUT

2

Source: Fast-growing hierarcy