Archiwum zadań programistycznych WWSI

Dużymi krokami zbliża się 2 maja, Dzień Flagi Rzeczypospolitej Polskiej. Z tej okazji mieszkańcy Zapluskowęsów postanowili całkowicie okryć frontowe ściany budynków flagami. Mieszkańcy każdego z domów mają zamiar przygotować własne flagi o kształcie kwadratu. Twoim zadaniem jest obliczenie ile flag będzie potrzebnych do okrycia każdego z n budynków.

Wejście

W pierwszej linii wejścia znajdują się jedna liczba całkowita n ∈ [1;125000] oznaczająca liczbę budynków w Zapluskowęsach. W kolejnych n liniach znajdują się po trzy liczby całkowite h ∈ [1;50], w ∈ [1;50] i r ∈ [1;50] oznaczające, że budynek, którego ściana frontowa ma h metrów wysokości i w metrów szerokości ma zostać pokryty flagami o rozmiarze r×r.

Wyjście

Na wyjściu należy, w osobnej linii, wypisać dla każdego z n domów minimalną liczbę flag jaka jest potrzebna do pokrycia jego ściany frontowej.

Przykład

Wejście

5
3 5 1
2 1 3
3 3 2
6 8 2
2 2 2

Wyjście

15
1
4
12
1