Как-то раз Кира нашел $$$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$$$.

Кира не очень силен в информатике, поэтому просит вас посчитать количество различных способов позвать друзей.