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 >

	qrst11: 2024-08-24 17:35:08 nice problem :)
	nadstratosfer: 2019-03-29 06:23:05 Downvoted for TL preventing submissions in slower languages, albeit from the comments I infer it's the fault of the SPOJ code recalculating limits after compiler update rather than psetters. With dataset containing a million numbers per case, O(n^2) would obviously fail at far more relaxed limit. Ignore earlier remarks regarding number of integers per line, the dataset appears to be formatted correctly now (as in there are n integers per line).
	chetan4060: 2018-01-09 20:55:50 nice problem with best concept;
	geoffreymace7: 2018-01-01 22:57:31 Same as http://www.spoj.com/problems/KOMPICI/ Strangely, my solution passed here at 0.13 s whereas in the former it passed at 0.32 s despite larger constraints.
	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

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