MACA (Moon Aviation and Cybernetics Agency) ļoti interesē pirmskaitļi. Vēl vairāk viņus interesē savstarpējie pirmskaitļi. Aģentūrai ir izdevies tikt pie daudziem skaitļiem un viņu mērķis ir noskaidrot, vai starp tiem ir savstarpēji pirmskaitļi.

Savstarpēji pirmskaitļi ir skaitļi, kur starp to dalītājiem vienīgais kopīgais dalītājs ir 1.

Palīdzi aģentūrai atrisināt šo problēmu.

Pirmajā rindā tiek dots skaitļu skaits 2 ≤ N ≤ 1000.

Nākamajā rindā tiek doti N skaitļi 1 ≤ a ≤ 10⁶.

Uzdevums ir izvadīt savstarpējos pirmskaitļu pārus sakārtotus pēc pirmā un otrā skaitļa augošā secībā. Katrs pāris jāizvada savā rindā. Tiek garantēts, ka vismaz viens pāris eksistē.

Testi ir sadalīti sekojošās grupās:

• 25% – 1 ≤ a ≤ 50.
• 100% – 1 ≤ a ≤ 10⁶.