Zadanie

Gorila Naďka

Počet bodov: 45

V Krajine Sladkých Pomarančov kvitne obchod s - presne tak - banánmi.

Madam záhradníčka obstaráva v strede lesa strom, ktorý je pevne stráženým tajomstvom jej rodiny už dlhé generácie. Je špeciálny tým, že na ňom vyrastie až \(N\) banánov.

Banány sú už zrelé, a trebalo by strom striasť, a banány odniesť do dediny na predaj.

Madam už má svoj vek, a otriasať strom či nosiť banány je už nad jej sily. Zvyčajne by jej pomohla rodina, tento rok sú však nanešťastie jej deti na dovolenke v Krajine Modrých Sliviek, a jej vnúčatá odcestovali na krajské kolo zenitu. Neostáva jej nič iné, ako si vypomôcť s rodinným maznáčikom, gorilou Naďkou.

Naďka je síce dostatočne silná, aby strom otriasla, vie však niesť len \(C\) banánov naraz. Zároveň je trochu nenažraná, a tak počas každého prejdeného kilometra si niekedy čorkne jeden banán z tých, čo nesie. Je nepredvídateľná, čiže naňho môže dostať chuť hneď zo začiatku, alebo na konci, alebo niekedy medzi tým. Ak by sa pritom stalo, že nemá so sebou banán, hodí tantrum, a už žiadne banány nosiť veru nebude.

To znamená, že nezvládne všetky banány odniesť do dediny na predaj - tá je vzdialená \(D\) kilometrov. Ale čo keby si Naďka odkladala banány aj cestou?

Úloha

Pri strome popadalo \(N\) banánov. Gorila Naďka vie niesť najviac \(C\) banánov naraz. Chceme čo najviac banánov preniesť do dediny, ktorá je vzdialená \(D\) kilometrov od stromu. Naďka si vie na každom celom kilometri odložiť banány, ktoré nosí (nevie si ich však odložiť medzi nimi). Zje pritom jeden banán za prejdený kilometer, a to v neznámych (a možno rôznych) momentoch. Nesmie sa stať, že pritom nemá banán poruke.

Koľko najviac banánov vie Naďka preniesť do dediny, ak si ich bude odkladať optimálne?

Vstup a Výstup

V prvom riadku je číslo \(t\) - počet paralelných vesmírov, v ktorích Madam potrebuje pomôcť.

V každom z nasledovných \(t\) riadkov sú tri čísla \(1 \leq N, D, C\).

Platí \(1 \leq t\leq 100\) a \(N, C \leq 10^9\).

V prvej sade \(D \leq 2\).

V druhej sade \(D \leq 20\). V tretej sade \(D \leq 10^5\).

Príklad

Input:

3
5 2 3
30 10 10
300 100 100

Output:

1
5
53

V prvom vesmíre môže Naďka zobrať 3 banány, prejde 1km pri čom prvý zje, druhý položí, vráti sa a cestou zje tretí. Následne zoberie zvyšné dva banány, počas prvého kilometra jeden zje, zoberie si odložený, počas druhého kilometa jeden zje a v cieli jej ostal jeden. Iná možnosť je že zoberie 3, cestou dva zje a do ciela donesie ten tretí.