Intervalos de silêncio

Time limit: 3000 msMemory limit: 256 MB

Dois alarmes tocam periodicamente. O primeiro toca nos instantes $a,2a,3a,\ldots$ , e o segundo nos instantes $b,2b,3b,\ldots$ .

Considere o intervalo de tempo $[0,T]$ . Marque os instantes $0$ , $T$ e todos os instantes de toque que pertencem a esse intervalo. Marcas coincidentes são uma única marca.

As marcas consecutivas dividem $[0,T]$ em intervalos de comprimentos $d_1,d_2,\ldots,d_m$ . Calcule

$d_1^2+d_2^2+\cdots+d_m^2.$

Para $T=0$ , a soma é zero. Responda a várias consultas independentes.

Input

A primeira linha contém um inteiro $q$ ( $1\le q\le 1\,000$ ).

Cada uma das próximas $q$ linhas contém três inteiros $a$ , $b$ e (, ).

Output

Para cada consulta, imprima uma linha com a soma dos quadrados dos comprimentos, como inteiro exato. O resultado pode ultrapassar o intervalo de um inteiro de 64 bits.

Samples

Sample 1

Input

Output

24
36
0

Na primeira consulta, as marcas são $0,3,5,6,9,10$ , gerando comprimentos $3,2,1,3,1$ e soma $24$ . Na segunda, as marcas são , gerando soma .