cmmmc

Definim noţiunea de pereche ordonată, perechea de numere naturale $(x,y)$ cu $x \leq y$. Definim cel mai mic multiplu comun al unei perechi ordonate ca fiind cel mai mic multiplu comun al numerelor care formează perechea.
Se dau $k$ numere naturale $n_1, n_2, \dots, n_k$.

Cerinţă

Să se determine pentru fiecare dintre numerele $n_i (i = 1, 2, \dots ,k)$ :

1. câte perechi ordonate au cel mai mic multiplu comun egal cu $n_i$.
2. dintre acestea, perechea ordonată care are suma minimă.

Date de intrare

Prima linie a fişierului cmmmc.in conţine un număr natural $k$.Următoarele $k$ linii din acest fişier vor conţine câte un număr natural; linia $i + 1$ va conţine numărul $n_i (i = 1, 2, ..., k)$.

Date de ieșire

Fişierul cmmmc.out va conţine $k$ linii. Pe fiecare dintre acestea se vor afla trei numere. Cele trei numere de pe linia $i$ vor reprezenta:

• primul, numărul de perechi ordonate care au cel mai mic multiplu comun egal cu $n_i$;
• următoarele două, numerele care alcătuiesc perechea ordonată care are cel mai mic multiplu comun egal cu $n_i$ şi a căror sumă este minimă, afişate în ordine crescătoare.

Restricții și precizări

• $1 \leq k \leq 100$
• $1 \leq n_i \leq 2 \ 000 \ 000 \ 000$
• Pentru $20\%$ dintre teste, $k \leq 100$ şi $n_i \leq 1 \ 000$
• Fiecare dintre cele $k$ linii ale fişierului cmmmc.out trebuie să conţină exact trei numere separate prin câte un spaţiu; în caz contrar, soluţia se consideră greşită şi se obţin $0$ puncte pentru testul respectiv. Rezolvarea corectă a cerinţei $1$ valorează $40\%$ din punctajul unui test, iar rezolvarea corectă a cerinţei $2$ valorează $60\%$.

Exemplu

cmmmc.in

2
10
11

cmmmc.out

5 2 5
2 1 11

Explicație

Există cinci perechi distincte care au cel mai mic multiplu comun egal cu $10$: $(1, 10)$, $(2, 10)$, $(5, 10)$, $(2, 5)$, $(10, 10)$. Dintre acestea perechea cu cea mai mică sumă este $(2, 5)$.
Pentru $n = 11$ există două perechi ordonate care au cel mai mic multiplu comun $11$: $(1, 11)$, $(11, 11)$. Dintre acestea perechea cu cea mai mică sumă este $(1, 11)$.