Link は $m$ 個の分銅を持っており、各分銅の重さは正の整数である。

Link はこれらの分銅を使って、$1$ から $n$ までのすべての整数重量を量ることができることがわかっている（分銅は天秤の片側にのみ置くことができる）。Link が持っている分銅のうち、最も重い分銅の重さは少なくともいくらか？

注意：Link が持っている分銅で $n+1$ 以上の重量を表現できるかどうかは不明である。

入力

各テストファイルには複数のテストケースが含まれる。1行目にテストケースの数 $T$ ($1 \le T \le 2 \times 10^5$) が与えられる。各テストケースの形式は以下の通りである。

1行目に2つの整数 $n$ と $m$ ($1 \le n, m \le 10^9$) が与えられる。これらは、分銅で表現可能な既知の最大重量と、分銅の個数を表す。

出力

各テストケースについて、Link が持っている最も重い分銅の重さの最小値を1行で出力せよ。もし $m$ 個の分銅を使って $1$ から $n$ までのすべての重量を表現することが不可能な場合は、"-1" を出力せよ。

入出力例

入力 1

2
40 6
16 4

出力 1

13
-1