Problema A - Somas de Quadrados

Diofanto de Alexandria foi um dos mais importantes matemáticos gregos. Conhecido por vezes como o "pai da Álgebra", está para a Aritmética como Euclides está para a Geometria, ou Ptolomeu para a Astronomia, por exemplo. Diofanto, que terá vivido no terceiro século da nossa era, contribuiu com muitas inovações, em particular na notação matemática e foi o primeiro matemático grego a perceber que as fracções são números. O seu trabalho mais conhecido é Aritmética, um colecção de 130 problemas algébricos e suas soluções numéricas que teve uma influência tremenda na matemática como nós a conhecemos. A sua tradução mais conhecida para latim foi feita por Bachet em 1621.

Entre as muitas descobertas fascinantes, Diofanto parecia já saber que todos os números inteiros positivos podem ser escritos como uma soma de no máximo quatro quadrados de outros números inteiros positivos. Este teorema, conhecido inicialmente como Conjectura de Bachet (precisamente por causa de Bachet ter feito a tradução), interessou as maiores mentes matemáticas da altura mas nem mesmo Fermat conseguiu prová-lo. A primeira prova acabou por aparecer em 1770, por Lagrange, confirmando a sua total validade. Vejamos alguns exemplos de números inteiros escritos como somas de quadrados:

  22 = 22 + 32 + 32 
  32 = 42 + 42
  74 = 52 + 72

Existem contudo várias formas de se escrever o mesmo número como soma de quadrados. O número 50, por exemplo, pode ser escrito de cinco maneiras diferentes:

  50 = 12 + 72
  50 = 52 + 52
  50 = 32 + 42 + 52
  50 = 12 + 22 + 32 + 62
  50 = 32 + 32 + 42 + 42

Repara que nas diferentes hipóteses existem um número diferente de quadrados a serem somados. Estamos interessados apenas em saber qual a mínima quantidade de quadrados a usar, que neste caso são dois quadrados. E dentro desse mínimo de hipóteses, quantas maneiras diferentes existem de fazer a soma? Neste caso temos precisamente duas maneiras, que correspondem às duas primeiras linhas. Nota que para efeitos de contagem a ordem em que os quadrados aparecem na soma não importa, pelo que 50 = 1² + 7² é a mesma coisa que 50 = 7² + 1² (só é contado uma vez).

No caso geral, para um dado número, consegues calcular estas informações? Qual o mínimo número de quadrados a usar? E qual o número de maneiras diferentes de fazer essa soma com esse mínimo de quadrados?

O Problema

Dado um número N, a tua tarefa é calcular o menor número K de quadrados que somados igualam N. Além disso, tens de calcular também de quantas maneiras diferentes D essa soma pode ser feita com K quadrados (a ordem em que os quadrados aparecem na soma não importa para efeitos de contagem).

Input

Na primeira linha de input vem um número inteiro C, indicando o número de casos a considerar (1 ≤ C ≤ 10).

Seguem-se exactamente C linhas, cada uma delas contendo um único número N indicando o número a considerar em cada caso (1 ≤ N ≤ 2 000 000).

Output

O output é constituído exactamente por C linhas, cada uma contendo a resposta para o número correspondente pela mesma ordem em que apareciam no input.

Cada uma dessas linhas deve vir no formato "N: K D" (sem as aspas). N é o número correspondente. K deve indicar o menor número de quadrados que somados igualam N. D deve indicar de quantas maneiras diferentes essa soma pode ser obtida com K quadrados. Nota que não importa a ordem em que os quadrados aparecem na soma, como foi atrás descrito. É garantido que D é sempre menor que 2³¹ e como tal cabe num normal inteiro de 4 bytes.

Nota sobre a Avaliação

Para um conjunto de casos de teste valendo 40% dos pontos, os números N a considerar serão menores ou iguais a 5 000.

Exemplo de Input

3
4
5
50

Exemplo de Output

4: 1 1
5: 2 1
50: 2 2