Uolevi ja Maija pelaavat peliä, jossa on n pussia ja m palloa. Kaikki pallot ovat samanlaisia, ja pussista ei näe, montako palloa siinä on.

Aluksi Uolevi päättää, miten hän jakaa pallot pusseihin. Hän laittaa jokaisen pallon johonkin pusseista. Uolevi muistaa, montako palloa kussakin pussissa on. Sitten Maija sekoittaa pussien järjestyksen.

Lopuksi Uolevi tekee joukon siirtoja. Joka siirrolla hän osoittaa yhtä pusseista. Jos pussi ei ole tyhjä, Maija antaa Uoleville yhden pallon pussista. Joka siirron jälkeen Uolevi päättää, mitä hän tekee seuraavaksi.

Mikä on pienin siirtomäärä, jolla Uolevi saa varmasti ainakin k palloa?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku t: testien määrä.

Tämän jälkeen syötteessä on t riviä, joista jokainen sisältää kokonaisluvut n, m ja k.

Tuloste

Ohjelmasi tulee tulostaa jokaista testiä kohden yksi kokonaisluku: pienin riittävä siirtomäärä.

Esimerkki

Syöte:

3
3 2 1
2 5 5
2 4 2

Tuloste:

2
6
2

Ensimmäisessä tapauksessa Uolevi laittaa pallot eri pusseihin. Tämän jälkeen hän tekee kaksi siirtoa ja osoittaa eri pusseihin. Ainakin toisessa pussissa on varmasti pallo, joten Uolevin tavoite onnistuu.

Toisessa tapauksessa Uolevi laittaa kaikki pallot samaan pussiin. Jos hän arvaa ensimmäisellä siirrolla pussin, jossa pallot ovat, hän saa ne viidellä siirrolla. Muuten hän vaihtaa heti pussia, ja kuluu yhteensä kuusi siirtoa.

Kolmannessa tapauksessa Uolevi laittaa kumpaankin pussiin kaksi palloa. Silloin hän voi nostaa kummasta tahansa pussista suoraan kaksi palloa.

Osatehtävä 1 (17 pistettä)

• 1 \le t \le 1000
• 1 \le n \le 20
• 1 \le k \le m \le 20

Osatehtävä 2 (49 pistettä)

• 1 \le t \le 1000
• 1 \le n \le 5000
• 1 \le k \le m \le 5000

Osatehtävä 3 (34 pistettä)

• 1 \le t \le 1000
• 1 \le n \le 10^9
• 1 \le k \le m \le 10^9