Abhi loves chocolates! He visits the Binary Bakery to buy some of his favorite chocolates. The owner of the bakery, Bobby, is a clever man. He does not want Abhi to finish all his chocolates. Hence, he plays a game. The Abhi is given N numbers and has to select K of these numbers. For each number that Abhi chooses, he will get as many chocolates as the number of 1's in the Binary representation of the number i.e. the number of bits that are set. Help Abhi find the maximum number of cakes that he can have.

Input:

The first line of input contains T. T test cases follow.

First line of each test cases contains 2 space-separated integers N and K.

The next line contains N space-separated integers.

Output:

For each test cases, print the answer in a new line.

Constraints:

1 ≤ T ≤ 10

1 ≤ N ≤ 103

0 ≤ K ≤ N

0 ≤ Numbers ≤ 105