408112: GYM102986 H Coprime Ribs

Butchering Farmer John's cows always yields great short ribs, but Old MacDonald (the co-owner of FJ's farm) has found a way to bring their flavor to even greater heights! Each of FJ's cows produces short ribs of a particular type, which is represented by some natural number. It turns out that pairing short ribs taken from different cows with short rib types that share no common factors other than $$$1$$$ creates a sublime contrast in flavor.

Old MacDonald wants to count the number of pairs of cows that can be used in the pursuit of his ideal short rib plate. Can you help him?

The first line of input contains a single integer $$$N$$$ ($$$1 \leq N \leq 100000$$$), the number of cows on the farm. The second line of input contains $$$N$$$ space separated integers $$$x_i$$$, where $$$x_i$$$ ($$$1 \leq x_i \leq 1000000$$$) is the rib type of the $$$i$$$-th cow.

Output a single integer representing the number of optimal short rib pairings by Old MacDonald's standards.

8
1 2 3 4 5 6 7 8

21