Kolejka recenzji składa się z $n$ prac naukowych, z których $m$-ta praca została złożona przez autora. Początkowo wartość naukowa tej pracy wynosi 1.

Gra rozpoczyna się ruchem autora, po czym strony wykonują ruchy naprzemiennie. W każdym ruchu gracz musi wykonać następujące operacje:

1. Pobierz kolejno $k$ prac z początku kolejki recenzji. Jeśli w kolejce pozostało mniej niż $k$ prac, pobierz wszystkie pozostałe.
2. Spośród pobranych prac wybierz 0 lub 1 pracę, aby ją opublikować lub trwale odrzucić, co oznacza jej całkowite usunięcie z kolejki.
3. Wszystkie pozostałe nieusunięte prace wstaw z powrotem na koniec kolejki w dowolnej kolejności. Ponieważ kolejka recenzji jest w pełni jawna, obie strony dokładnie znają nową pozycję każdej pracy po ponownym wstawieniu.

Wynik końcowy autora zależy od losu jego pracy: Jeśli w trakcie ruchu praca nie została usunięta i została ponownie wstawiona na koniec kolejki, jej wartość naukowa wzrasta o 1. Jeśli autor w trakcie swojego ruchu dobrowolnie usunie swoją pracę, zostaje ona pomyślnie opublikowana, gra kończy się natychmiast, a autor otrzymuje aktualną wartość naukową pracy. * Jeśli recenzent w trakcie swojego ruchu usunie tę pracę, zostaje ona trwale odrzucona, gra kończy się natychmiast, a autor otrzymuje 0 punktów.

Celem autora jest maksymalizacja wyniku, natomiast celem recenzenta jest minimalizacja wyniku autora.

Oblicz końcowy wynik autora, zakładając, że obie strony stosują strategie optymalne.

Wejście

Każdy zestaw danych zawiera wiele przypadków testowych. Pierwsza linia zawiera liczbę całkowitą $T$ ($1 \le T \le 50$), oznaczającą liczbę przypadków testowych. Dla każdego przypadku testowego: * Pierwsza linia zawiera trzy liczby całkowite $n, k, m$ ($1 \le n, k \le 10^9$, $1 \le m \le n$), oznaczające odpowiednio długość kolejki recenzji, liczbę pobieranych prac oraz początkową pozycję pracy autora.

Wyjście

Dla każdego przypadku testowego wypisz w jednej linii liczbę całkowitą oznaczającą końcowy wynik autora. W szczególności, jeśli gra nigdy się nie kończy, wypisz $-1$.

Przykład

Wejście 1

6
3 2 1
5 3 4
10 3 1
7 3 7
817247666 7237 327476688
610723117 332458760 292738094

Wyjście 1

2
0
2
4
3470
278264358