using System.Collections.Generic; using System.Linq; using System; public static class combi { public static IEnumerable> Comb(this IEnumerable items, int r) { if (r == 0) { yield return Enumerable.Empty(); } else { var i = 1; foreach (var x in items) { var xs = items.Skip(i); foreach (var c in Comb(xs, r - 1)) yield return c.Before(x); i++; } } } public static IEnumerable Before(this IEnumerable items, T first) { yield return first; foreach (var i in items) yield return i; } } public class Hello { static void Main() { var n = int.Parse(Console.ReadLine().Trim()); var a = new int[n]; for (int i = 0; i < n; i++) a[i] = int.Parse(Console.ReadLine().Trim()); getAns(n, a); } static void getAns(int n, int[] a) { var count = 0; var b = Enumerable.Range(0, n).Comb(3); foreach (var x in b) { var c = x.ToArray(); var k0 = Gcd(a[c[1]], a[c[2]]); if (k0 == 1) { count++; continue; } var k1 = Gcd(a[c[0]], k0); if (k1 == 1) count++; } Console.WriteLine(count); } static int Gcd(int a, int b) { if (a < b) return Gcd(b, a); while (b != 0) { var w = a % b; a = b; b = w; } return a; } }