A. Банк SauSaGe
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Все жители города SauSaGe обсуждают его знаменитый банк, который предлагает, казалось бы, невозможную сделку:

"Оставьте свои деньги у нас, и мы будем удваивать их каждый день!"

Хамед решает попробовать и кладёт $$$1$$$ доллар на свой счёт.

Пусть в начале некоторого дня на его банковском счёте лежит $$$x$$$ долларов. Каждый день по порядку происходят следующие события:

  1. Утром банк волшебным образом удваивает его баланс, и на счёте становится $$$2x$$$ долларов.
  2. Ночью Хамед может снять все деньги со своего банковского счёта. Если он это делает, снятая сумма поступает на его карту, а на банковском счёте сразу снова становится $$$1$$$ доллар, чтобы на следующий день процесс удвоения начался заново. В противном случае он оставляет деньги в банке.

К сожалению, этот невероятный банк будет открыт ровно $$$n$$$ дней, после чего закроется навсегда.

Хамед хочет снять деньги ровно в $$$k$$$ различных дней до закрытия банка. Определите максимальную сумму денег, которая может оказаться на карте Хамеда после $$$n$$$-го дня.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1\le k\le n\le30$$$).

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

Для каждого набора входных данных выведите одно целое число — максимальную сумму денег, которая может оказаться на карте Хамеда после $$$n$$$-го дня.

Пример
Входные данные
5
1 1
2 1
4 3
5 5
10 2
Выходные данные
2
4
8
10
514
Примечание

В первом наборе входных данных в первый день на его банковском счёте становится $$$2$$$ доллара, и он решает снять их.

Во втором наборе входных данных он может снять деньги в $$$2$$$-й день.

В третьем наборе входных данных он может снять деньги в $$$1$$$-й, $$$3$$$-й и $$$4$$$-й дни. Он получает $$$2$$$, $$$4$$$ и $$$2$$$ доллара соответственно.