Как-то раз Кира нашел \(n\) друзей из Морио и решил собрать их за одним столом, чтобы провести мирный разговор. Рост друга \(i\) равен \(a_i\). Так получилось, что рост каждого из друзей уникален.
Но вот незадача, в доме Киры всего \(3\) стула, и всех друзей усадить явно не удастся! Поэтому Кира должен позвать только \(3\) друзей.
Но все не так просто! Если рост самого низкого и самого высокого из приглашенных друзей не взаимно просты, то друзья будут подшучивать друг над другом, что сильно разозлит Киру.
Кира заинтересовался, сколько есть способов позвать \(3\) друзей так, чтобы они не стали подшучивать друг над другом? Два способа считаются различными, если существует такой друг, что он приглашен в одном случае, и не приглашен в другом.
Формально, если Кира позовет друзей с номерами \(i\), \(j\) и \(k\), то должно выполняться \(\gcd(\min(a_i, a_j, a_k), \max(a_i, a_j, a_k)) = 1\), где \(\gcd(x, y)\) обозначает наибольший общий делитель (НОД) чисел \(x\) и \(y\).
Кира не очень силен в информатике, поэтому просит вас посчитать количество различных способов позвать друзей.
Примечание
В первом примере подходит одна способ — позвать друзей \(1\), \(2\) и \(3\). Здесь \(1 < 2 < 3\), и числа \(1\) и \(3\) взаимно просты.