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
lumaks_69: 2022-03-11 20:29:52

numbers are indeed distinct

feodorv: 2020-09-13 19:56:18

We have:
1. all input numbers are distinct
2. we should determine how many integers in the array are twice of some other integers in the same array
Alas we should count zero number in the input (2 * 0 = 0) though it is the same integer (not 'some other' integer)

roopammishra: 2019-01-09 00:14:18

Binary Search worked!!:)

dewa251202: 2018-10-29 08:39:49

my solution assumes that the testcases has only distinct values and it got accepted :/

mag1x_: 2018-06-26 15:08:10

Don't trust spojtoolkit on this one :/

coderanant: 2017-12-13 07:36:01

Completely Wrong
The no can be double of itself also...
ty:Filip Sollar

bsiddhartha: 2017-06-20 18:39:20

tq :) filip Sollar

Filip Sollar: 2017-04-11 16:44:33

The problem statement is incorrect the numbers in the array are not DISTINCT !!! and it could also be double of the same integer !!! this costed me many WAs, correct output for
4
0 0 0 0 is 4 not 3 as you should deduce from "output the count of the integers that are double of some other integer."
also O(n^2) solution

sushanth_r: 2017-01-25 15:38:59

is N really the number of 'distinct' integers in the array?
No, it isn't. The integers in the array can be equal.
O(n^2) is accepted with 0.0s

Last edit: 2017-01-25 16:25:55
vengatesh15: 2017-01-24 16:23:05

simple one..


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