НОД объединяет

문제

На одну из кафедр филфака университета Байтландии поступили $nn$ студентов. Поскольку они совершенно не знакомы друг с другом, им необходимо найти способ быстро и надежно передавать друг другу информацию о предстоящих экзаменах и зачётах.

Для этого студенты создадут несколько диалогов в новом Байтландском мессенджере. В каждом диалоге будет участвовать ровно два студента. Информация будет распространяться следующим образом: после того, как один из студентов узнал о предстоящей контрольной работе, он рассылает это сообщение во все диалоги со своими одногруппниками. После этого все те люди, которым он разослал сообщения и которые его ещё не получали, рассылают сообщение во все диалоги, в которых они участвуют и так далее.

Староста загорелся идеей построить сеть диалогов таким образом, чтобы каждый получил сообщение хотя бы один раз. При этом он хочет, чтобы количество диалогов было минимально возможным. Поскольку таких вариантов всё ещё очень много, староста придумал свою странную оценку качества сети диалогов: каждому человеку из группы он сопоставил число $a_{i}a\_i$. Он считает, что оценка одного диалога, созданного между одногруппником $uu$ и одногруппником $vv$, равна $\text{НОД}(a_u,a_v)НОД(a\_u,\; a\_v)$, где $\text{НОД}(x,y)НОД(x,\; y)$ --- наибольший общий делитель чисел $xx$ и $yy$, то есть максимальное целое положительное $dd$, которое делит и $xx$, и $yy$. Староста хочет, чтобы суммарная оценка всех диалогов была как можно больше.

Помогите старосте найти максимальную суммарную оценку!

입력

В первой строке входных данных дано единственное число $nn$ ($1\le n\le 1000001\; \backslash le\; n\; \backslash le\; 100\backslash ,000$) --- количество студентов на кафедре филфака университета Байтландии.

Во второй строке даны $nn$ целых положительных чисел $a_{i}a\_i$ ($1\le a_i\le 10000001\; \backslash le\; a\_i\; \backslash le\; 1\backslash ,000\backslash ,000$) --- числа, которые староста сопоставил студенту.

출력

Выведите единственное целое число --- максимальную суммарную оценку сети, которую может построить староста, при условии, что количество диалогов в сети будет минимально.

힌트

В первом примере оптимальным ответом будет создать диалог между следующими парами студентов: $(1,2)(1,\; 2)$, $(2,3)(2,\; 3)$, $(2,4)(2,\; 4)$, $(4,5)(4,\; 5)$. Суммарная оценка такой сети диалогов равняется $1+1+2+1=51\; +\; 1\; +\; 2\; +\; 1\; =\; 5$.