E. Quarentena de Códigos
Um laboratório armazena n amostras, cada uma identificada por um inteiro positivo ai. Duas amostras são consideradas compatíveis se o máximo divisor comum de seus códigos é 1.
Uma amostra será retirada temporariamente. Para cada índice i, determine quantos pares não ordenados de índices distintos (j,k), com j<k e j,k != i, continuariam compatíveis depois da retirada da amostra i. Amostras de mesmo código continuam sendo objetos diferentes.
Input
A primeira linha contém n. A segunda contém n inteiros a1, ..., an.
Restrições:
1 ≤ n ≤ 200000; 1 ≤ ai ≤ 200000. As respostas cabem em inteiro de 64 bits.
Output
Imprima n inteiros: a quantidade de pares compatíveis restantes após retirar cada amostra, em ordem.
Samples
Sample 1
Input
4 2 3 4 5
Output
3 2 3 2
Retirando as amostras 1, 2, 3 e 4, restam respectivamente 3, 2, 3 e 2 pares de códigos coprimos.