prietene

Numerele naturale nenule $x$ și $y$ se numesc prietene dacă au același număr de divizori primi.

Cerințe

Fiind date două șiruri de numere naturale, primul cu $n$ numere, iar al doilea cu $m$ numere, scrieți un program care rezolvă următoarele cerințe:

1. Determină cel mai mare dintre cele n+m numere date ce are număr maxim de divizori primi.
2. Determină câte perechi de numere prietene de forma $(x,y)$ se pot forma, $x$ fiind din primul șir, iar $y$ din al doilea șir.

Date de intrare

Fişierul de intrare prietene.in conţine pe prima linie numărul $C$ reprezentând cerința ($1$ sau $2$), pe a doua linie numerele $n$ și $m$, pe a treia linie un șir de $n$ numere, iar pe a patra linie un șir de $m$ numere, numerele de pe fiecare linie fiind separate prin câte un spațiu.

Date de ieșire

Dacă $C=1$, atunci pe prima linie a fişierului de ieşire prietene.out se va scrie numărul ce reprezintă răspunsul la cerința $1$.
Dacă $C=2$, atunci pe prima linie a fişierului de ieşire prietene.out se va scrie numărul ce reprezintă răspunsul la cerința $2$.

Restricții și precizări

• $1 \leq n,m \leq 10^4$
• Cele două șiruri conțin numere naturale din intervalul $[2,10^9]$.
• Pentru $30\%$ din teste cerinţa va fi $C=1$.
• $10$ puncte se acordă din oficiu.

Exemplul 1

prietene.in

1
3 4
36 30 5
12 60 13 77

prietene.out

60

Explicație

Pentru fiecare număr din șirurile date scriem numărul de divizori primi: $36 \rightarrow 2$, $30 \rightarrow 3$, $5 \rightarrow 1$, $12 \rightarrow 2$, $60 \rightarrow 3$, $13 \rightarrow 1$, $77 \rightarrow 2$
Numărul maxim de divizori primi este $3$. Cel mai mare număr din șirurile date care are $3$ divizori primi este $60$.

Exemplul 2

prietene.in

2
4 5
36 30 5 10
12 60 15 77 105

prietene.out

8

Explicație

Sunt $8$ perechi de numere prietene: $(36,12)$, $(36,15)$, $(36,77)$, $(10,12)$, $(10,15)$, $(10,77)$, $(30,60)$, $(30,105)$