Definim noţiunea de pereche ordonată, perechea de numere naturale (x,y) cu x ≤ 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 n1, n2, … , nk.
Cerinţă
Să se determine pentru fiecare dintre numerele ni (i=1,2,…,k):
a) câte perechi ordonate au cel mai mic multiplu comun egal cu ni.
b) 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 ni (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 ni;
- următoarele două, numerele care alcătuiesc perechea ordonată care are cel mai mic multiplu comun egal cu ni şi a căror sumă este minimă, afişate în ordine crescătoare.
Restricţii
• 1 ≤ k ≤ 100
• 1 ≤ ni ≤ 2 000 000 000
• Pentru 20% dintre teste, k ≤ 100 şi ni ≤ 1000
Exemple
cmmmc.in
cmmmc.out
Explicaţii
2
10
11
5 2 5
2 1 11
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).