Fişierul intrare/ieşire:	magic3.in, magic3.out	Sursă	Algoritmiada 2014, Runda Finala
Autor	Andrei Heidelbacher	Adăugată de	Heidelbacher Andrei •a_h1926
Timp execuţie pe test	0.05 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Magic3

Tassadar vrea să devină mentalist şi s-a hotărât să înveţe un truc pe care să i-l arate prietenului său, Zeratul. Se consideră numerele naturale de la 1 la N şi o constantă K (1 <= K < N). Zeratul trebuie să se gândească la un număr natural X (1 <= X <= N), iar Tassadar poate efectua întrebări de forma "Numărul X la care te-ai gândit se află în mulţimea { a₁, a₂, ..., a_K }?" (mulţimea trebuie să conţină K numere naturale distincte din intervalul [1, N]).
După un anumit număr de întrebări, Tassadar va ghici prin magie numărul la care s-a gândit Zeratul.
Deoarece nu vrea să-şi plictisească prietenul cu prea multe întrebări, vă roaga să-i spuneţi care este numărul minim de întrebări pe care trebuie să le pună, în cel mai rău caz, pentru a ghici numărul la care s-a gândit Zeratul.

Date de intrare

Fişierul de intrare magic3.in conţine pe prima linie numărul de teste T. Pe următoarele T linii se vor afla câte două numere N şi K cu semnificaţia din enunţ.

Date de ieşire

În fişierul de ieşire magic3.out veţi afişa T numere reprezentând raspunsul pentru fiecare test, câte unul pe linie.

Restricţii

• 1 ≤ T ≤ 10⁴
• 2 ≤ N ≤ 10⁹
• 1 ≤ K < N

Exemplu

Cum se trimit solutii?