Annettuna on lista, jossa on n positiivista kokonaislukua.

Tehtäväsi on laskea, monellako tavalla listalta voidaan valita kaksi lukua niin, että niiden suurin yhteinen tekijä on 1.

Syöte

Ensimmäisellä rivillä on kokonaisluku n: listan lukujen määrä.

Toisella rivillä on n lukua x_1,x_2,\dots,x_n: listan sisältö.

Tuloste

Tulosta yksi kokonaisluku: tehtävän vastaus.

Esimerkki

Syöte:

8
5 4 20 1 16 17 5 15

Tuloste:

19

Osatehtävä 1 (12 pistettä)

• 1 \le n \le 100
• 1 \le x_i \le 100

Osatehtävä 2 (35 pistettä)

• 1 \le n \le 10^5
• 1 \le x_i \le 100

Osatehtävä 3 (53 pistettä)

• 1 \le n \le 10^5
• 1 \le x_i \le 10^6