Longest Subsequence with Common Digits

Given a sequence of \( N \) numbers, find the length of the longest subsequence such that every consecutive pair of numbers in the subsequence share at least one common digit.

For a subsequence \( a_{1}, a_{2}, \ldots, a_{k} \) of the original sequence, it must hold that for every \( 2 \leq i \leq k \), the sets of digits in \( a_{i-1} \) and \( a_{i} \) have a non-empty intersection. In other words, if we denote by \( D(x) \) the set of digits present in the integer \( x \), then the condition is:

[ \forall, 2 \leq i \leq k, \quad D(a_{i-1}) \cap D(a_{i}) \neq \emptyset. ]

Your task is to compute the maximum length \( k \) possible for any such subsequence extracted from the given sequence.

inputFormat

The first line contains an integer \( N \) representing the number of elements in the sequence. The second line contains \( N \) space-separated integers representing the sequence.

outputFormat

Output a single integer representing the length of the longest subsequence meeting the criteria.

3
123 234 345

3