IITKWPCH  Find Number Of Pair of Friends
You are given n numbers. Any two number are called friends if they have some digit common. eg. (11, 12) and (15, 4561) are friends but (33, 556) is not.
Find out no of pairs which are friends.
(Formally speaking Let us assume the n numbers be are stored in array a[]. You have to find out number of i and j pairs such that i < j and a[i] and a[j] are friends.).
Input
T : no of test cases (T >= 1 && T <= 7)
For each test case, you will be given two lines, first line will contain n <= 10^6
then in next n line each line will contain a single integer representing a[i] (a[i] >= 1 && a[i] <= 10^18)
Output
For every test case print a line
containing number of such pairs as mentioned in the problem statement.
Example
Input: 4
2
12 13
3
10 12 24
3
5 6 7
4
10 11 211 3
Output:
1
2
0
3
hide comments
Shubham:
20150701 13:12:45
nyc problem.... learnt a lot :) 

kartikay singh:
20150604 07:31:49
learned something new :)


ANUJ RATHORE:
20150601 12:09:02
will O(n2) pass?


ggkjh:
20140805 19:09:37
considering a[i] as a string of size 25 got AC...in 0.53 sec..where as considering a[i] as a long long data type got AC in 1.78 sec...Can anyone justify the reason for this weird behavior...????


Sir_Ostara:
20140116 16:16:15
TLE..taking input as string and using printf and scanf. help??


Luka:
20131231 11:00:06
KOMPICI 

Piyush Kapoor:
20131226 14:05:12
I remember this question was a part of Directi coding contest for hiring at MNNIT Allahabad. 

praveen123:
20130911 07:05:33
@Mayank, My completely unoptimized code in c++ took 0.5 sec. So I chose the time limit to 1 sec. If you are using some other language other than C,C++ then I can agree with your point but not with C,C++ for sure.


Mitch Schwartz:
20130911 07:05:33
@praveen123: Please check the formatting according to numerix's comment. Last edit: 20130911 03:34:24 

Federico LebrÃ³n:
20130911 07:05:33
EDIT: Removed. Last edit: 20130910 23:03:22 
Added by:  praveen123 
Date:  20130805 
Time limit:  0.318s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  general problem 