Pis rəqəm
Cohn və Brus hesab edirlər ki, N sayı çox pis bir rəqəmdir. Buna görə də onlar hər zaman və hər yerdə ondan qaçmağa çalışırlar.
İndi oğlanlar M sayını müsbət ədədlərin cəmi şəklində təqdim etmək istəyirlər, lakin hər bir ədəd K-dan çox olmamalıdır. Amma pis N sayını unutmaq olmaz! Hər bir cəm N-ə bölünməməlidir və cəmlərin sayı da N-ə bölünməməlidir.
Sizin vəzifəniz M sayını belə bir təqdimatda minimum mümkün cəm sayını tapmaqdır.
Məsələn, əgər N = 3, M = 11, K = 6 olarsa, biz M=5+6 kimi təqdim edə bilərik, amma 6 sayı 3-ə bölünür, deməli, bizdə ən azı 3 cəm olmalıdır. Lakin N = 3 olduğuna görə, bizdə 3 cəm ola bilməz və buna görə də cavab 4 olacaq. M sayını təqdim etməyin mümkün yollarından biri:
11 = 4 + 4 + 2 + 1.
Giriş verilənləri
Birinci sətir bir tam ədəd T - testlərin sayını ehtiva edir. Hər bir test bir sətirdən ibarətdir və üç tam ədəd N, M və K ehtiva edir, bir boşluqla ayrılmışdır.
Çıxış verilənləri
Hər bir test üçün yuxarıda təsvir edilən tələblərə uyğun olaraq minimum mümkün cəm sayını ehtiva edən bir sətir çıxarın. Əgər bu mümkün deyilsə, "-1" (tırnaqsız) çıxarın.
Məhdudiyyətlər
1 <= T <= 74,
1 <= N, M, K <= 1000000000 (10^9).