The Digit GCD ArrayMedium

The Digit GCD Array

Medium+40 XP · +15 Auramathnumber theorygcd

UptoSkills Arena is organizing a coding contest where participants submit their solutions. Each submission has a unique ID, which is a positive integer. The contest organizers want to analyze the relationship between the submission IDs based on the greatest common divisor (GCD) of the sum of their digits. They are interested in pairs of distinct submissions whose IDs have a sum of digits that share a common factor greater than 1.

Given an array of submission IDs, find the number of distinct pairs of indices (i, j) such that i < j and the greatest common divisor of the sum of digits of A[i] and the sum of digits of A[j] is greater than 1.

Input

The first line contains an integer n, the number of submissions. The next line contains n space-separated integers A_1, A_2, ..., A_n representing the submission IDs.

Output

Print a single integer, the total count of pairs (i, j) with i < j such that gcd(sum_of_digits(A[i]), sum_of_digits(A[j])) > 1.

Constraints

1 <= n <= 200000 1 <= A_i <= 10^9

Time limit 1 s (native code; slower languages get more)Memory 256 MB14 hidden tests

Example 1

Input
5
12 34 56 78 90
Output
3

Sums of digits are: 3, 7, 11, 15, 9. Pairs with GCD > 1: (3, 9) gcd=3, (15, 9) gcd=3. Total = 2.

Example 2

Input
4
2 4 6 8
Output
6

Sums of digits are: 2, 4, 6, 8. All pairs have GCD > 1. Total = 6.

Hints