Physics Class

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
The Physics teacher in Tanu's class is teaching concepts of a bouncing ball. The rubber ball that she is using has the property that if the ball is dropped from height H then, it bounces back to maximum height H/F. So after first bounce it rises up to maximum height H/F, after second bounce to maximum height H/F^{2}, after third bounce to maximum height H/F^{3}, and so on.
The class has N children, and the teacher wants to select two children such that when the taller child drops the ball from his height, ball reaches a maximum height equal to the height of the shorter child after some (possibly zero) number of bounces. Note that zero bounces mean heights of the two children will be same. Given the heights of the children in the class Height[i], can you tell how many ways are there for the teacher to select two children for the demonstration? Note that when heights are same, the pair is only counted once (See first example for further clarification).
Input
First line contains T, number of testcases. Then 2*T lines follow, 2 per testcase.
First line of each testcase consists of two spaceseparated intergers N and F. Second line of each testcase contains N spaceseparated integers representing the array Height.
Output
For each testcase, print a single line containing the answer to the problem.
Constraints
 For 40 points: 1 ≤ T ≤ 100, 1 ≤ N ≤ 10^{3}, 2 ≤ F ≤ 10^{9}, 1 ≤ Height[i] ≤ 10^{9}
 For 60 points: 1 ≤ T ≤ 100, 1 ≤ N ≤ 10^{4}, 2 ≤ F ≤ 10^{9}, 1 ≤ Height[i] ≤ 10^{9}
Example
Input:
2
3 2
2 2 2
3 2
2 1 4
Output:
3
3
Explanation:
 In the first case, the three pairs are (child 1, child 2), (child 2, child 3) and (child 1, child 3).
 For the second case also, the three pairs are (child 1, child 2), (child 2, child 3) and (child 1, child 3).
Author:  piyushkumar 
Tester:  xiaodao 
Editorial  http://discuss.codechef.com/problems/PHYSICS 
Tags  binarysearch, hashmap, ltime17, piyushkumar, simpleeasy, sorting 
Date Added:  1102014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions