Description

Given $N$ positive integers $A_1, A_2, ..., A_N$, find how many integer pairs $(i, j)$ satisfy the following conditions:

• $1 \le i < j \le N$.
• $A_i$ and $A_j$ share at least one common digit (the digit does not need to be in the same position).

Input Format

The first line contains a positive integer $N$.

The next $N$ lines each contain a positive integer $A_i$.

Output Format

Output one integer in a single line, representing the number of pairs that satisfy the condition.

3
4
20
44

1

4
32
51
123
282

4

Hint

Sample Explanation

In Sample 1, the pair that meets the requirement is $(1, 3)$.

In Sample 2, the pairs that meet the requirement are $(1, 3)$, $(1, 4)$, $(2, 3)$, $(3, 4)$.

Constraints

For $100\%$ of the testdata, $1 \le N \le 10^6$, $1 \le A_i \le 10^{18}$.

Notes

The scoring of this problem follows the original COCI settings, with a full score of $120$.

This problem is translated from COCI2011-2012 CONTEST #2 T4 KOMPIĆI.

Translated by ChatGPT 5