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

Описание

Перед вами мифическая гидра: у неё n типов голов, пронумерованных от 1 до n (от «нижних» к «верхним»). При ударе по голове одного типа эта голова отрубается, но у гидры тут же возникают дополнительные головы, причём каждая голова создаёт копию голов других типов (могут появиться головы того же типа). Ваша задача — добить гидру, то есть добиться нулевого количества голов всех типов, затратя минимальное число ударов. Нулевым количеством считается тот момент, когда после сруба последней головы, другие головы не будут появляться.

Вход

На вход подаётся набор данных. Первая строка содержит число n — количество типов голов гидры (1 ≤ n ≤ 2000). Далее идёт строка, содержащая массив a из n элементов a_1 ... a_n (0 ≤ a_i ≤ 10^9) — начальные количества голов. Затем подаётся n строк по n целых чисел, задающих матрицу b.

Выход

Одно целое число — минимальное общее количество ударов, необходимое для уничтожения всех голов гидры. Если гидру невозможно убить, выведите -1

Примеры

Пример 1

Вход:

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

Выход:

• 4

Пример 2

Вход:

• 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

Выход:

• 31

Пример 3:

Вход:

• 1
• 1
• 1

Выход:

• -1

Описание

Тетрация — это бинарная операция, описанная как ʸx=xˣ(y раз)ˣ. Иными словами, тетрация является повторяющимся возведением в степень. В стрелочной нотации — x^^y. Цель — посчитать x^^y.

• На вввод подаётся два числа x (1<=x<=1234), y (0<=y<=2)
• В единственной строке вывода — число у y —ответ на задачу.

Ввод, вывод

Пример 1

Ввод

2 2

Вывод

4

Пример 2

Ввод

5 0

Вывод

1

Пример 3

Ввод

6 2

Вывод

46656

Источник: Tetration

Стас играет в очень сложную математическую игру I wanna be the professor. Она похожа на I wanna be the Guy, но для продвижения нужно помимо умения играть, ещё и считать различные выражения. И вот он дошёл до босса, где ему нужно считать быстрорастущую иерархию из числа n (1<=n<=100) по индексу a (0<=a<=5). Помогите Стасу пройти этого босса.

Входные Данные

На ввод подаётся два числа: n и a

Выходные данные

Вывести число f — ответ на задачу

Пример

ВВОД

0 1

ВЫВОД

2

Источник: Fast-growing hierarcy