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