Link posiada $m$ odważników, z których każdy ma wagę będącą liczbą całkowitą dodatnią. Wiadomo, że Link może za pomocą tych odważników odmierzyć każdą wagę całkowitą od $1$ do $n$ (odważniki można umieszczać tylko na jednej szalce wagi). Jaka jest minimalna możliwa waga najcięższego odważnika, jaki posiada Link? Uwaga: Nie wiadomo, czy odważniki Linka pozwalają na odmierzenie wagi $n+1$ lub większej.

Wejście

Każdy plik testowy zawiera wiele zestawów danych. Pierwsza linia zawiera liczbę zestawów danych $T$ ($1 \le T \le 2 \times 10^5$). Format każdego zestawu danych jest następujący: Pierwsza linia zawiera dwie liczby całkowite $n$ oraz $m$ ($1 \le n, m \le 10^9$), oznaczające maksymalną wagę, którą można odmierzyć, oraz liczbę posiadanych odważników.

Wyjście

Dla każdego zestawu danych wypisz w jednej linii liczbę całkowitą oznaczającą minimalną możliwą wagę najcięższego odważnika. Jeśli nie jest możliwe odmierzenie wszystkich wag od $1$ do $n$ za pomocą $m$ odważników, wypisz "-1".

Przykład

Wejście 1

2
40 6
16 4

Wyjście 1

13
-1