Cerința

Se dă un șir de n perechi de numere naturale nenule. Să se determine câte perechi de numere au proprietatea că cele două numere din pereche au aceiași factori primi, indiferent de puterea acestora în descompunerea în factori primi.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n perechi de numere naturale.

Date de ieșire

Programul va afișa pe ecran numărul de perechi care îndeplinesc condiția din cerință.

Restricții și precizări

• 1 ≤ n ≤ 1000
• valorile din cele n numere citite vor fi mai mici decât \(2^{31}\)

Exemplu:

Intrare

4
12 18
16 12
18 30
25 35

Ieșire

1

Explicație:

Numărul 12 are ca factori primi pe 2 și pe 3, la fel și 18. Celelate perechi de numere nu resprectă proprietatea cerută.