У Link есть $m$ гирь, вес каждой из которых является положительным целым числом. Известно, что Link может использовать эти гири для взвешивания любого целого веса от $1$ до $n$ (гири можно класть только на одну чашу весов). Каков минимально возможный вес самой тяжелой гири, которая есть у Link? Примечание: неизвестно, могут ли гири, имеющиеся у Link, составить вес $n + 1$ или больше.

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

Каждый файл содержит несколько наборов входных данных. Первая строка содержит количество наборов данных $T$ ($1 \le T \le 2 \times 10^5$). Формат каждого набора данных следующий: Первая строка содержит два целых числа $n$ и $m$ ($1 \le n, m \le 10^9$), обозначающих максимальный известный вес, который можно составить, и количество гирь соответственно.

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

Для каждого набора данных выведите одну строку с целым числом — минимально возможным весом самой тяжелой гири у Link. Если невозможно составить все веса от $1$ до $n$ с помощью $m$ гирь, выведите «-1».

Примеры

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

2
40 6
16 4

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

13
-1