Laiko ribojimas: 1s

Atminties ribojimas: 1024MB

Duomenų failas: 2018_stovykla_vyr_dezute.in

Rezultatų failas: 2018_stovykla_vyr_dezute.out

Jei norite pateikti savo sprendimą - prisijunkite.

Dėžutė

Linas labai mėgsta dovanoti įvairias dovanas savo draugams. Kiekviena iš jo dovanų yra supakuota į dėžutę, kurią įpakavo pats Linas.

Visas dėžutes Linas įpakuoja į dovanų popierių, kuris yra iškirptas iš vieno didesnio a\\timesb matmenų popieriaus lakšto (a ir b -- sveikieji skaičiai). Jei tiksliau:

  1. Linas pradeda su a\\timesb matmenų popieriaus lakštu (jei a\\leq2 arba b\\leq2 Linas lapą išmeta);
  2. Linas pasirenka sveikąjį skaičių 1\\leqx\\leqmin(a,b)/2 ir iš kiekvieno pirminio lakšto kampo iškerpa x\\timesx dydžio kvadratėlį;
  3. Iš likusio lapo Linas sukuria x\\times(a-2x)\\times(b-2x) tūrio dėžutę (dėžutė neturi viršutinės plokštumos);
  4. Šiuos veiksmus Linas rekursiškai kartoja su keturiais iškirptais x\\timesx kvadratėliais.

Linas bando pasirinkti visus x (atliekant žingsnį 2., jis gali pasirinkti naują skaičių) taip, kad apvyniotų dėžučių tūrių suma būtų kiek įmanoma didesnė.

Užduotis

Parašykite programą, kuri, turėdama pradinio popieriaus laško matmenis, rastų maksimalią dėžučių tūrių sumą.

Pradiniai duomenys

Pirmoje eilutėje įrašyti testų skaičių 1\\leqT\\leq10^4. Likusiose T eilučių pateikta po du skaičius 1\\leqa_i,b_i\\leq10^6.

Rezultatai

Jums reikės išvesti T skaičių v_i -- maksimalią galimą iškirptų dėžučių tūrių sumą, kai pirminis popieriaus lašktas yra a\\timesb.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
5
3 3
6 7
10 7
5 9
18 9
 
1
20
40
21
140