题目描述

SauSaGe 城的每个人都在谈论这里著名的一家银行，它提供了一个看似不可能的交易： “把你的钱存在我们这儿，我们每天都会让它翻倍！”

Hamed 决定试一试，于是他在账户中存入了 $1$ 美元。

假设在某一天开始时，他的银行余额是 $x$ 美元。每一天都会按顺序发生以下事件：

1. 在早晨，银行奇迹般地将他的余额翻倍，变成 $2x$ 美元。
2. 在晚上，Hamed 可以选择将银行账户里的所有钱全部取出。如果他这么做，取出的金额会加到他的银行卡上，并且他的银行账户会立即重置为 $1$ 美元，以便第二天重新开始翻倍过程。如果他不取款，钱就留在银行里继续翻倍。

不幸的是，这家不可思议的银行只会在接下来的 $n$ 天内营业，之后将永久关闭。

Hamed 希望在银行关闭前，恰好在 $k$ 个不同的日子里进行取款。请计算在第 $n$ 天结束后，Hamed 银行卡上的金额最大能达到多少。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 500$）—— 测试用例的数量。

对于每个测试用例，仅包含一行，有两个整数 $n$ 和 $k$（$1 \le k \le n \le 30$）—— 分别表示银行营业的天数和 Hamed 取款的天数。

输出格式

对于每个测试用例，输出一行一个整数，表示在第 $n$ 天结束后 Hamed 银行卡上能够达到的最大金额。

样例输入 1

5
1 1
2 1
4 3
5 5
10 2

样例输出 1

2
4
8
10
514

说明

样例解释

• 在第一个测试用例中，他的银行余额在第一天变成了 $2$，然后他选择了取款，获得 $2$ 美元。
• 在第二个测试用例中，他可以选择在第 $2$ 天取款。此时余额翻倍了两次（$1 \to 2 \to 4$），他获得 $4$ 美元。
• 在第三个测试用例中，他可以选择在第 $1$、第 $3$ 和第 $4$ 天取款。
  • 第 $1$ 天：余额 $1 \to 2$，取出 $2$ 美元，余额重置为 $1$。
  • 第 $2$ 天：余额 $1 \to 2$，不取款。
  • 第 $3$ 天：余额 $2 \to 4$，取出 $4$ 美元，余额重置为 $1$。
  • 第 $4$ 天：余额 $1 \to 2$，取出 $2$ 美元。 他分别获得了 $2, 4, 2$ 美元，总计 $8$ 美元。

数据范围

• 对于所有测试点，保证 $1 \le t \le 500$。
• 对于每个测试用例，保证 $1 \le k \le n \le 30$。
• 保证所有的输入数值均为整数。