AU7_1 - PAIRS

no tags 

Given an array of N large integers up to 20 digits each, find pairs of integers that have at least one digit in common (not necessarily in same position.)

Input

First line contains T (1 <= T <= 10) number of test cases. Followed by description of each test case. The first line of each test case contains an integer N (1 <= N <= 1000000) followed by N large integers.

Output

Find number of pairs that have at least one digit in common (not necessarily in same position.)

Example

Input:
1
4
32
51
123
282

Output:
4

Explanation

These are the pairs.

  • 32, 123
  • 32, 282
  • 51, 123
  • 123, 282


Added by:arun
Date:2013-05-08
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: BF