最轻的最大砝码

题目描述

Y 同学有一个天平和 $m$ 个砝码。

天平的一侧只能放置砝码，另一侧只能放置待称量的物品。因此，若选择若干个砝码放在天平上，则能够称出的重量等于这些砝码的重量之和。

每个砝码的重量都是 $[1,n]$ 范围内的正整数，不同砝码的重量可以相同。

Y 同学希望通过这 $m$ 个砝码，能够分别称出重量为

$1,2,\dots,n$

的所有物品。

也就是说，对于任意 $1\le x\le n$，都必须能够从这 $m$ 个砝码中选择若干个，使所选砝码的重量之和恰好为 $x$。每个砝码在一次称量中最多使用一次。

在所有满足上述要求的砝码配置方案中，Y 同学希望最重的那个砝码尽可能轻。

请你求出最重砝码重量的最小可能值。

如果不存在满足要求的砝码配置方案，则输出 $-1$。

输入格式

第一行包含一个正整数 $T$，表示测试数据组数。

接下来 $T$ 行，每行包含两个正整数 $n,m$，分别表示需要能够称出的最大重量和砝码数量。

输出格式

对于每组测试数据，输出一行一个整数。

如果存在满足要求的砝码配置方案，输出其中最重砝码重量的最小可能值。

如果不存在满足要求的方案，输出 $-1$。

样例

样例输入 #1

2
40 6
16 4

样例输出 #1

13
-1

数据范围与约定

对于 $100$ 的数据，保证：

• $1\le T\le10^5$；
• $1\le n,m\le10^9$。

• 特殊性质 A：保证 $n=2^m-1$。
• 特殊性质 B：保证 $m\le30$。
• 特殊性质 C：保证 $m\le60$。