Fişierul intrare/ieşire:	present.in, present.out	Sursă	RMI 2021
Autor	Tamio-Vesa Nakajima	Adăugată de	Tamio Vesa Nakajima •tamionv
Timp execuţie pe test	0.5 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Present

Laika a decis să îi facă un cadou prietenei ei Azusa, vrăjitoarea din munţi. Din motive pe care nu le cunoaştem, cadoul va fi o mulţime finită de numere întregi pozitive. Ar fi o chestiune simplă să alegi un cadou, dar mai mulţi factori complică această sarcină.

În primul rând, duşmanul lui Laika, Flatorte, are puteri magice misterioase: dându-se două numere întregi x şi y ea poate crea cel mai mare divizor comun al lui x şi y (i.e. gcd(x, y)). Dacă Laika oferă un cadou în care Flatorte ar putea să adauge măcar un element (i.e. dacă oferă mulţimea A pentru care x, y apartin lui A, dar gcd(x, y) nu apartine lui A), atunci Flatorte poate imediat să îşi tachineze rivalul. Din aceste motive, cadoul lui Laika nu trebuie să poată fi îmbunătăţit cu ajutorul puterilor lui Flatorte: dacă ea oferă mulţimea A atunci pentru orice x, y ce apartin lui A trebuie să fie satisfăcută condiţia că gcd(x, y) apartine lui A.

În al doilea rând, Laika vrea ca cadoul ei să aibă o semnificaţie specială. Au trecut exact K zile de când a cunoscut-o pe Azusa şi ea vrea ca cadoul să indice acest lucru. De aceea Laika a aranjat toate mulţimile care satisfac condiţia explicată mai sus în ordine Laikană (explicată mai jos), obţinând astfel un şir infinit de mulţimi finite S₀, S₁, .... Ea vrea să selecteze ca cadou mulţimea S_K. Puteţi să o ajutaţi să îndeplinească această sarcină?

Ordine Laikană. Selectăm două mulţimi A şi B. Atunci, A apare înaintea lui B în ordinea Laikană dacă şi numai dacă max A < max B, sau max A = max B şi A - { max A } apare înaintea lui B - { max B } în ordinea Laikană. În scopul acestei definiţii, fie max {} = -infinit. Observaţi că această ordine este întotdeauna bine definită pentru mulţimi finite de numere întregi pozitive.

Date de intrare

Prima linie de input conţine un număr întreg T-numărul de teste. Fiecare din următoarele T linii conţin o valoare K pentru care noi vrem să aflăm S_K.

Date de ieşire

Pentru fiecare T valori a lui K, afişaţi mulţimea S_K. Pentru a afişa o mulţime, afişaţi o linie care începe cu numărul de elemente a mulţimii, iar apoi elementele acesteia, în ordine crescătoare.

Restrictii

• 1 ≤ T ≤ 5
• Pentru 8 puncte, 0 ≤ K ≤ 100.
• Pentru 21 puncte, 0 ≤ K ≤ 1 000 000.
• Pentru 41 puncte, 0 ≤ K ≤ 500 000 000.
• Pentru 14 puncte, 0 ≤ K ≤ 1000 000 000.
• Pentru 16 puncte, 0 ≤ K ≤ 1500 000 000.

Exemple

Explicatii

Observaţi că S₀ = {}, S₁ = {1}, S₂ = {2}, S₃ = {1, 2}, S₄ = {3}, S₅ = {1, 3}, S₆ = {1, 2, 3}, S₁₀₀ = {1, 2, 3, 7, 8}, S₁₀₀₀ = {1, 2, 3, 5, 10, 11, 12}. Acestea sunt exact mulţimile afişate în exemplu (împreună cu mărimile lor). Observaţi că S₆ != {2, 3} --- deaorece 2, 3 apartin lui {2, 3}, dar gcd(2, 3) = 1 ce nu apartine lui {2, 3}.

Cum se trimit solutii?