Một cặp số ~(x, y)~ được gọi là cặp số bạn bè nếu ở biểu diễn thập phân, ~(x, y)~ có ít nhất một chữ số giống nhau. Ví dụ ~(11, 12)~ và ~(15, 4561)~ là cặp số bạn bè, nhưng ~(33, 556)~ thì không.

Cho dãy ~n~ số nguyên ~a_1, a_2, \dots, a_n~. Hãy cho biết có bao nhiêu cặp chỉ số ~i < j~ sao cho ~(a_i, a_j)~ là cặp số bạn bè.

Input

Gồm nhiều test case, dòng đầu tiên của dữ liệu vào chứa số nguyên ~t~ ~(1 \leq t \leq 7)~ cho biết số bộ test.

Các dòng sau mô tả ~t~ bộ test, mỗi bộ test có dạng:

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \leq n \leq 10^6)~ - kích thước của dãy số.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(1 \leq a_i \leq 10^{18})~, mô tả dãy số.

Output

In ra ~t~ dòng, mỗi dòng chứa đáp án của bộ test tương ứng.

Scoring

• Subtask 1 ~(50\%)~: ~1 \leq n \leq 1000~
• Subtask 2 ~(100\%)~: Không có ràng buộc gì thêm.

Sample Input

4
2
12 13
3
10 12 24
3
5 6 7
4
10 11 211 3

Sample Output

1
2
0
3