CNTDO - Count Doubles

no tags 

You are given an array of integers. Your task will be to determine how many integers in the array are twice of some other integers in the same array. For example, consider an array:

1 3 4 7 9 2 18

Here answer is 3 as 2 is twice of 1, 4 is twice of 2 and 18 is twice of 9.

Input

The first line of the input will be an integer T (T ≤ 1000) to represent the number of test cases. Each test case will contain two lines. The first line contains integer N (1 ≤ N ≤ 1000) which indicates the number of distinct integers in the given array. The second line contains N integers and each integer will not be greater than 10000 by its absolute value.

Output

In a single line, output the count of the integers that are double of some other integer.

Example

Input:
2
7
1 3 4 7 9 2 18
3
1 4 3

Output:
3
0

hide comments
rajeev_mnnit: 2016-08-17 23:23:10

poor test cases...

mishra_sharad: 2016-08-15 20:31:43

please make sure ur logic must include -ve numbers otherwise........

hodobox: 2016-08-12 15:34:35

N^2 passes. Sigh. Maybe move this to tutorial and make a version where N<=10^5, |a[i]|<=10^9, so you can't just implement the brutest of bruteforces?

Jacob Plachta: 2016-08-09 22:20:29

"double of some other integer" is incorrect, it could be double of the same integer

anhkhoa: 2016-07-27 04:50:45

i only need one punch to accepted this problem

mkfeuhrer: 2016-07-07 12:06:17

question in which i performed most silly mistake :-/
costed me many WA ..!!
read the ques carefully ..... its easy
and yes neg no. allowed !! and 0*2=0!

Sarthak Munshi: 2016-07-04 20:34:46

man ! easy problem ! the extra blank lines in sample i/o costed me many WAs !

Akshat Jain: 2016-07-04 14:00:42

real easy...just take care there can be negative numbers as well!

deadbrain: 2016-07-01 18:04:45

Read the question properly. Costed me several unsuccessful submissions. :(

pulkitgulati: 2016-07-01 14:11:03

easiest problem ever solved on spoj!!!!!


Added by:Akid Sultan
Date:2016-06-30
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY