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.*; 
import java.util.StringTokenizer; 
import java.io.PrintWriter;
import java.io.*;

import java.util.stream.Collectors.*;
import java.lang.*;
import static java.util.stream.Collectors.*;
import static java.util.Map.Entry.*;
public class Ideo
{ 
    static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }
   
static class aksh
{
    
    int x;
    int y;
    int moves;

    public aksh(int a,int b,int c) 
    {
        x = a;
        y = b;
        moves=c;
    }
}
static int power(int x,int y) 
{ 
    int res = 1;      // Initialize result 
  
      // Update x if it is more than or  
                // equal to p 
  
    while (y > 0) 
    { 
        // If y is odd, multiply x with result 
        if (y%2==1) 
            res = (res*x); 
  
        // y must be even now 
        y = y>>1; // y = y/2 
        x = (x*x);   
    } 
    return res; 
} 
 
 static int gcd(int a, int b) 
    { 
        if (a == 0) 
            return b; 
        return gcd(b % a, a); 
    } 


  static boolean compareSeq(char[] S, int x, int y, int n) 
    { 
        for (int i = 0; i < n; i++)
         {

            if (S[x] < S[y]) 
               return true;
            else if (S[x] > S[y]) 
                return false; 
            x = (x + 1) % n; 
            y = (y + 1) % n; 
        } 
        return true; 
    } 

    static void build(long[] sum,int[] arr,int n)
    {
      for(int i=0;i<(1<<n);i++)
      {
        long total=0;
        for(int j=0;j<n;j++)
        {
          if((i & (1 << j)) > 0)
            total+=arr[j];
        }

        sum[i]=total;
      }
    }

 
     static int count(long arr[], long x, int n) 
       {

        int l=0;
        int h=n-1;

        int res=-1;
        int mid=-1;
        while(l<=h)
        {
          mid=l+(h-l)/2;
          if(x==arr[mid])
          {
            res=mid;
            h=mid-1;
          }
          else if(x<arr[mid])
            h=mid-1;
          else
            l=mid+1;
        }

        if(res==-1)
          return 0;

        //res is first index and res1 is last index of an element in a sorted array total number of occurences is (res1-res+1)

        int res1=-1;
        l=0;
        h=n-1;
        while(l<=h)
        {
          mid=l+(h-l)/2;
          if(x==arr[mid])
          {
            res1=mid;
            l=mid+1;
          }
          else if(x<arr[mid])
            h=mid-1;
          else
            l=mid+1;
        }



        if(res1==-1)
          return 0;
        if(res!=-1 && res1!=-1)
          return (res1-res+1);

        return 0;

       } 

       static int parity(int a)
       {
    a^=a>>16;
    a^=a>>8;
    a^=a>>4;
    a^=a>>2;
    a^=a>>1;
    return a&1;
  }
/*
  PriorityQueue<aksh> pq = new PriorityQueue<>((o1, o2) -> {
            if (o1.p < o2.p)
                return 1;
            else if (o1.p > o2.p)
                return -1;
            else
                return 0;

        });//decreasing order acc to p*/
static int power(int x, int y, int m)  
    { 
        if (y == 0) 
            return 1; 
          
        int p = power(x, y / 2, m) % m; 
        p = (p * p) % m; 
      
        if (y % 2 == 0) 
            return p; 
        else
            return (x * p) % m; 
    } 
static int modinv(int a, int m) 
    { 
        int g = gcd(a, m); 
        if (g != 1) 
            return 0;
        else 
        { 
           return power(a, m - 2, m); 
        } 
        //return 0;
    } 

static int[] product(int[] nums) {
    int[] result = new int[nums.length];
 
    int[] t1 = new int[nums.length];
    int[] t2 = new int[nums.length];
 
    t1[0]=1;
    t2[nums.length-1]=1;
 
    //scan from left to right
    for(int i=0; i<nums.length-1; i++){
        t1[i+1] = nums[i] * t1[i];
    }
 
    //scan from right to left
    for(int i=nums.length-1; i>0; i--){
        t2[i-1] = t2[i] * nums[i];
    }

    for(int i=0;i<nums.length;i++)
      {
        System.out.print(t1[i]+" "+t2[i]);
        System.out.println();
      }
 
    //multiply
    for(int i=0; i<nums.length; i++){
        result[i] = t1[i] * t2[i];
    }
 
    return result;
}

static int getsum(int[] bit,int ind)
{
  int sum=0;
  while(ind>0)
  {
    sum+=bit[ind];
    ind-= ind & (-ind);
  }

  return sum;
}

static void update(int[] bit,int max,int ind,int val)
{
  while(ind<=max)
  {
    bit[ind]+=val;
    ind+= ind & (-ind);
  }
}

    static ArrayList<Integer>[] adj;
    static int[] bfs(ArrayList<Integer>[] adj,int n,ArrayList<Integer> arr)
    {
      int[] vis=new int[n];
      int[] dis=new int[n];
      int[] par=new int[n];
      Queue<Integer> q=new LinkedList<>();

      Arrays.fill(dis,-1);

      for(int i=0;i<arr.size();i++)
      {
        vis[arr.get(i)]=1;
        dis[arr.get(i)]=0;
        par[arr.get(i)]=-1;
        q.add(arr.get(i));
      }

      while(!q.isEmpty())
      {
        int x=q.remove();
        for(int u:adj[x])
        {
          if(vis[u]==0)
          {
            vis[u]=1;
            dis[u]=dis[x]+1;
            par[u]=x;
            q.add(u);
          }
        }
      }

      return dis;
    }

    static boolean check(long mid,long a,long b)
    {
      long count=1;
      while(count<=mid)
      {
        count++;
        if(a<b)
          a+=count;
        else
          b+=count;

        if(a==b)
          return true;
      }
        return false;
    }

    static class a1
    {
      long p;
      int q;

      public a1(long p,int q)
      {
        this.p=p;
        this.q=q;
      }
    }
    public static void main(String args[] ) throws Exception 
    {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT */

         FastReader sc=new FastReader();
         int t=sc.nextInt();
         char[] ch={'R','G','B'};

         while(t-->0)
         {
          
          int n=sc.nextInt();
          TreeSet<Integer> even=new TreeSet<>();

          for(int i=0;i<n;i++)
          {
            int x=sc.nextInt();

            if(x%2==0)
            even.add(x);
          }

          int c=0;

         while(!even.isEmpty())
          {
            c++;
            int x=even.pollLast();
            x/=2;
            if(x%2==0)
              even.add(x);
          }

                     

          System.out.println(c);
          

         }
        

  

      }

    }


