Prihlásenie Registrácia  

M - Suma podielov

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

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

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

Martin má už náhodne lietajúcich intervalov po krk a rozhodol sa odreagovať pri celočíselnom delení s radmi.
Zvolil si čísla N a M, postupne vyrátal hodnoty 0*N div M, 1*N div m, ... (M-1)*N div M a všetky tieto potom sčítal. Keď však boli čísla veľmi veľké, aj táto hra, ako inak, sa zmenila na nočnú moru, ktorá akoby nikdy nekončila.
Vedeli by ste mu pomôcť? Nebude totiž spokojný, kým nebude schopný vyrátať túto funkciu aj pre skutočne veľké čísla.

Úloha

Pre dané čísla N a M vypočítajte sumu celočíselného podielu (i*N)/M pre i=0, ... , M-1

Vstup

V prvom riadku súboru sa nachádza číslo Q udávajúce počet sád.

Nasleduje Q riadkov s dvojicou čísel N a M.

1 ≤ Q ≤ 100 000
1 ≤ M,N ≤ 100 000 000

Výstup

Výstupom programu je odpoveď na každú sadu na samostatnom riadku.

Príklad

Vstup:

2
2 2
5 8

Výstup:

1
14