H - Khepri

Časový limit: 3s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3.4, Python 3.11

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Ako všetci faraóni od kráľa Džósera chcel byť aj mladý faraón Chufev pochovaný v pyramíde. Aj on si želal, aby bola jeho pyramída ešte väčšia a majestátnejšia ako všetky predošlé.
Pyramídy mali tvar ihlanu so štvorcovou podstavou. Spodná vrstva pyramídy mala šírku N kvádrov. Dokopy tak obsahovala N² kvádrov. Šírka každej ďalšej vrstvy bola o jeden kváder menšia ako šírka predchádzajúcej vrstvy. Najvyššia vrstva na vrchole pyramídy takto obsahovala už len jediný kváder.
Na stavbu pyramíd sa v tom čase používali vápencové kvádre, ktoré sa vylamovali v kameňolome na východnom brehu Nílu. Khepri, vtedajší majiteľ kameňolomu, sa v snahe predať čo najviac kvádrov rozhodol predávať kvádre v balení po M kusov.
Kráľ Chufev sa rozhodol použiť na stavbu svojej pyramídy len kvádre (balenia po M kusov) z Khepriho kameňolomu, pričom kúpi najmenší počet balení, ktorý bude postačovať na stavbu.

Úloha

Dané sú dve prirodzené čísla N a M. N je šírka základne pyramídy a M je počet kvádrov v jednom balení. Vypíšte počet použitých kvádrov z posledného balenia.

Vstup

Vstup bude v prvom riadku obsahovať jedno prirodzené číslo T zodpovedajúce počtu testovacích vstupov (1≤T≤1000).
Každý z nasledujúcich T riadkov bude obsahovať dve medzerou oddelené prirodzené čísla N a M (1≤N≤1 000 000 000, 1≤M≤10000).

Výstup

Pre každú dvojicu N M vypíšte prislúchajúci počet zvyšných kvádrov (číslo z intervalu 0...(M-1)). Váš výstup by mal obsahovať T čísel, každé v samostatnom riadku.

Príklad

Príklad vstupu

4
5 2
6 8
1 1
999999998 10

Príklad výstupu

Poznámka: Na stavbu prvej pyramídy potrebujeme 5²+4²+3²+2²+1² = 25+16+9+4+1 = 55 kvádrov.

01 Finále 2