SPOJ.com - Problem IITKWPCH

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) are not.

Find out the number of pairs which are friends.

(Formally speaking let us suppose the n numbers 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 : number of test cases (1 ≤ T ≤ 7)
For each test case, you will be given two lines, first line will contain n <= 10⁶, then the next line will contain n integers representing a[i] (1 ≤ a[i] ≤ 10¹⁸.)

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

Submit solution!

hide comments

< Previous 1 2 3 Next >

	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
	Mayank Raj: 2013-09-11 07:05:33 This question is not in the programming spirit! The time limit should be extended...provided you are running on a SILLY PENTIUM 3 machine...less than the computational power of an average smartphone. I had to struggle till eternity to optimize on the constants of the time complexity... The time limit should be such that THE CORRECT algorithm's descent implementation should work!
	Rishabh Sharma: 2013-09-11 07:05:33 Very nice problem!!! :)
	numerix: 2013-09-11 07:05:33 The input data is malformatted, which cost me a lot of WAs! The given number of values per line does not match with the real number of values per line. @Mitch: Thanks for clarification. So my initial algorithm was correct, but the successive WAs made me confused.
	Mitch Schwartz: 2013-09-11 07:05:33 @numerix: Every number is friends with itself, and the answer for your test case is 1.
	numerix: 2013-09-11 07:05:33 What is the exact meaning of "any two numbers"? Does that imply that those "two numbers" have to be different numbers? So, is the correct output for the following example 1 or 0? 1 2 3 3
	$iddharth prasad: 2013-09-11 07:05:33 can someone give some more test cases plzz ...
	Ouditchya Sinha: 2013-09-11 07:05:33 Awesome problem! :)

Submit solution!

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