There are n positive integers a_1, a_2, ..., a_n. For the one move you can choose any even value c and divide by two all elements that equal c.

For example, if a=[6,8,12,6,3,12] and you choose c=6, and a is transformed into a=[3,8,12,3,3,12] after the move.

You need to find the minimal number of moves for transforming a to an array of only odd integers (each element shouldn't be divisible by 2).

Input

The first line of the input contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases in the input. Then t test cases follow.

The first line of a test case contains n (1 ≤ n ≤ 2⋅10^5) — the number of integers in the sequence a. The second line contains positive integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9).

The sum of n for all test cases in the input doesn't exceed 2⋅10^5.

Output

For t test cases print the answers in the order of test cases in the input. The answer for the test case is the minimal number of moves needed to make all numbers in the test case odd (i.e. not divisible by 2).

Example

Input


4
6
40 6 40 3 20 1
1
1024
4
2 4 8 16
3
3 1 7


Output


4
10
4
0

Note

In the first test case of the example, the optimal sequence of moves can be as follows:

  * before making moves a=[40, 6, 40, 3, 20, 1]; 
  * choose c=6; 
  * now a=[40, 3, 40, 3, 20, 1]; 
  * choose c=40; 
  * now a=[20, 3, 20, 3, 20, 1]; 
  * choose c=20; 
  * now a=[10, 3, 10, 3, 10, 1]; 
  * choose c=10; 
  * now a=[5, 3, 5, 3, 5, 1] — all numbers are odd. 



Thus, all numbers became odd after 4 moves. In 3 or fewer moves, you cannot make them all odd.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Codeforces {

    static Scanner sc = new Scanner(System.in);
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static long GCD(long a,long b){
        if (b == 0)
            return a;
        return GCD(b,a%b);
    }

    static int highestPowerOf2(int n) {
        int p = (int)(Math.log(n) /
                Math.log(2));
        return (int)Math.pow(2, p);
    }

    public static int binSearch(long[] a,long x){
        int l = 0;
        int r = a.length - 1;
        while (l <= r){
            int mid = l + (r-l)/2;
            if (a[mid]==x)
                return 1;
            else if (a[mid] < x)
                l = mid+1;
            else
                r = mid-1;
        }
        return -1;
    }

    public static int upperBound(long[] arr,long key){
        int start=0;int end=arr.length-1;
        int idx=-1;
        int mid;
        while(start<=end){
            int i=(start+end)/2;
            if(arr[i]<key){
                start=i+1;
            }
            else if(arr[i]>key){
                end=i-1;
            }
            else{
                idx=i;
                start=i+1;
            }
        }

        return idx;    }

    public static int lowerBound(long[] arr,long key){
        int start=0;int end=arr.length-1;
        int idx=-1;
        int mid;
        while(start<=end){
            int i=(start+end)/2;
            if(arr[i]<key){
                start=i+1;
            }
            else if(arr[i]>key){
                end=i-1;
            }
            else{
                idx=i;
                end=i-1;
            }
        }
        return idx;
    }

    public static int searchInsert(long[] nums, long target) {
        int s=0,e=nums.length-1;
        int mid;
        if(target<nums[0]){
            return 0;
        }
        while(s<=e){
            mid=(s+e)/2;
            if(nums[mid]>target){
                e=mid-1;
            }
            else if(nums[mid]==target){
                return mid;
            }
            else{
                s=mid+1;
            }
        }
        return s;
    }

    public static class Pair<T1,T2>{
        T1 first;
        T2 second;
        Pair(T1 a,T2 b){
            this.first = a;
            this.second = b;
        }

        @Override
        public String toString() {
            return "[" + first + ", " + second + "]";
        }
    }

    static boolean isPrime(long n) {
        if (n <= 1)
            return false;
        if (n <= 3)
            return true;

        if (n % 2 == 0 || n % 3 == 0)
            return false;

        for (long i = 5; i <= Math.sqrt(n); i = i + 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;

        return true;
    }

    public static long fastExpo(long a,int n,int mod){
        if (n == 0)
            return 1;
        else{
            if ((n&1) == 1){
                long x = fastExpo(a,n/2,mod);
                return (((a*x)%mod)*x)%mod;
            }
            else{
                long x = fastExpo(a,n/2,mod);
                return (((x%mod)*(x%mod))%mod)%mod;
            }
        }
    }

    public static long modInverse(long n,int p){
        return fastExpo(n,p-2,p);
    }

    public static long nCr(int n,int r,long[] fact,int mod){
        long val =  (((fact[n] * modInverse(fact[r],mod))%mod)*modInverse(fact[n-r],mod))%mod;
        return val;
    }

    public static void factorial(long[] fact,int n,int mod){
        for (int i=1;i<=n;i++){
            fact[i] = (fact[i-1] * i)%mod;
        }
    }

    public static int log2(long val){
        return (int) Math.floor(Math.log(val)/Math.log(2));
    }

    public static boolean isSubSequence(String s,String t){
        int i = 0;
        int j = 0;
        while (i < s.length() && j < t.length()){
            if (s.charAt(i) == t.charAt(j))
                j++;
            i++;
        }
        return j == t.length();
    }

    public static void solve() throws IOException {
        int n = sc.nextInt();
        long[] a = new long[n];
        Map<Long,Integer> mp = new HashMap<>();
        for (int i=0;i<n;i++){
            a[i] = sc.nextLong();
            if (a[i]%2 == 0){
                mp.put(a[i],mp.getOrDefault(a[i],0) + 1);
            }
        }
        int ans = 0;
        ArrayList<Long> list = new ArrayList<>(mp.keySet());
        Collections.sort(list);
        //System.out.println(list);
        while (list.size() != 0){
            long key = list.get(list.size()-1);
            //System.out.println(key);
            int val = mp.get(key);
            mp.remove(key);
            while (!mp.containsKey(key) && key%2 == 0){
                //System.out.println("hello");
                key /= 2;
                //System.out.println(key);
                ans++;
            }
            if (mp.containsKey(key)){
                mp.replace(key,mp.get(key) + val);
                list.remove(list.size()-1);
            }
            else if (key%2 == 1){
                list.remove(list.size()-1);
            }
        }
        //System.out.println(list);
        System.out.println(ans);
    }
    public static void main(String[] args) throws IOException{
        int t;
        t = sc.nextInt();
        //t = 1;
        while (t-- > 0){
            solve();
        }
    }
}

