IITKWPCH - Find Number Of Pair of Friends

no tags 

    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: 2015-07-01 13:12:45

nyc problem.... learnt a lot :)

kartikay singh: 2015-06-04 07:31:49

learned something new :)
A very nice problem.....

ANUJ RATHORE: 2015-06-01 12:09:02

will O(n2) pass?

ggkjh: 2014-08-05 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...????

Any sort of correct justification is appreciated..:)

Last edit: 2014-08-05 19:10:59
Sir_Ostara: 2014-01-16 16:16:15

TLE..taking input as string and using printf and scanf. help??
got AC :)..just check the final datatype

Last edit: 2014-01-17 13:17:25
Luka: 2013-12-31 11:00:06

KOMPICI

Piyush Kapoor: 2013-12-26 14:05:12

I remember this question was a part of Directi coding contest for hiring at MNNIT Allahabad.

praveen123: 2013-09-11 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.
Increasing time limit to 2 sec.

Mitch Schwartz: 2013-09-11 07:05:33

@praveen123: Please check the formatting according to numerix's comment.

Last edit: 2013-09-11 03:34:24
Federico Lebrón: 2013-09-11 07:05:33

EDIT: Removed.

Last edit: 2013-09-10 23:03:22

Added by:praveen123
Date:2013-08-05
Time limit:0.318s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:general problem