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.stream.IntStream;
//Java Program to rearrange numbers in an Array
//such that no two numbers are adjacent

import java.util.Comparator;
import java.util.PriorityQueue;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;

import java.util.Arrays;
import java.util.List;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.math.BigInteger;
import java.util.Map;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

public class  Dragons{
   
	class Sol
	{
	    int countRev (String x)
	    {
	         Stack<Character> st=new Stack<Character>();
	            for(int i=0;i<x.length();i++){
	                
	                if(x.charAt(i)=='{'||x.charAt(i)=='('||x.charAt(i)=='['){
	                    st.add(x.charAt(i));
	                }else{
	                    if(st.size()>0){
	                    if(x.charAt(i)=='}' && st.peek()=='{'){
	                        st.pop();
	                    }else if(  x.charAt(i)==')' && st.peek()=='('){
	                        st.pop();
	                    }else if(x.charAt(i)==']' && st.peek()=='['){
	                    st.pop();
	                    }else{
	                       st.add(x.charAt(i));
	                    }
	                    }else{
	                       st.add(x.charAt(i));
	                    }
	                    
	                }
	                
	                
	            }
	             int count1=0;
	  int count2=0;
	            if(st.size()%2!=0){
	              return -1;
	            }else{
	                 Iterator value = st.iterator();
	 
	        while (value.hasNext()) {
	            if((char)value.next()=='}'){
	                count1++;
	            }
	        }
	        count2=st.size()-count1;
	        if(count1%2==0){
	            count1=count1/2;
	            
	        }else{
	            count1=count1/2;
	            count1+=2;
	            count2--;
	        }
	       
	        
	            }
	            return count1+((count2)/2);
	            
	    }
	}
	static ArrayList<ArrayList<Integer>> adjList;
	static boolean[] visit;
	static int max=0;
//	static ArrayList<ArrayList<Pair>> nodes;
	
	
    public static HashSet<Long> visited= new HashSet<>();
    public static long n;
    public static long m;
    public static boolean vis[][];
    public static int[] dist = new int[(int) 1e4+1];
    static long decimalToBinary(long N)
    {
     long w=0;
       while(N!=1) {
    	   N=N/2;
    	   w++;
        }
       return w;
     
        
    }
	public static void main(String[] args) throws IOException {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		while(n>0) {
			int p=sc.nextInt();
			
			HashSet<Integer> hs=new HashSet<Integer>();
			for(int i=0;i<p;i++) {
				int y=sc.nextInt();
				if(y%2==0) {
					hs.add(y);
				}
			}
			long count=0;;
			for(int i:hs) {
				while(i%2==0) {
					count++;
					if(hs.contains(i/2)) {
						break;
					}
					i=i/2;
				}
			}
			System.out.println(count);
		n--;
		}
		
	}
	static int  count(int a) {
	int b=0;
	while(a%2==0) {
		a=a/2;
		b++;
	}
	return b;
	}
	static long countDivisibles(long A, long B, long M)
    {
        // Add 1 explicitly as A is divisible by M
        if (A % M == 0)
            return (B / M) - (A / M) + 1;
 
        // A is not divisible by M
        return (B / M) - (A / M);
    }
	public static long findMax(long a) {
		long b=a;
		long max=Integer.MIN_VALUE;
		while(b>0) {
			max=Math.max(max,b%10);
			b=b/10;
			
		}
		
		return max;
	}
	public static long findMin(long a) {
		long b=a;
		long max=Integer.MAX_VALUE;
		while(b>0) {
			max=Math.min(max,b%10);
			b=b/10;
			
		}
		
		return max;
	}
	public static boolean check(int k,boolean []visited,int []arr) {
		for(int i=0;i<arr.length;i++) {
			if(!visited[arr[i]^k])
				return false;
		}
		return true;
	}
	static int Max(int arr[])
	{
		int max = arr[0];
		for(int i = 1; i < arr.length; i++)
			if(arr[i] > max)max = arr[i];
		
		return max;
	}
		
	// Function to return the maximum
	// count of pairs with equal sum
	static int maxCountSameSUM(int arr[], int n)
	{
		int maxi = Max(arr);
		
		// Create a map to store frequency
		int[] M = new int[2 * maxi + 1];
		
		
		for(int i = 0; i < M.length; i++)M[i] = 0;
	 
		// Store counts of sum of all
		// pairs in the map
		for (int i = 0; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) {
				M[(arr[i] + arr[j])] += 1;
			}}
		for(int i=0;i<M.length;i++) {
			System.out.print(M[i]+" ");
		}
		System.out.println();
		int max_count = 0;
	 
		// Find maximum count
		for (int i = 0; i < 2 * maxi; i++)
			if (max_count < M[i])
				max_count = M[i];
	 
		return max_count;
	}
//	
//	 static void compare(Pair arr[], long n2)
//	    {
//	        // Comparator to sort the pair according to second element
//	        Arrays.sort(arr, new Comparator<Pair>() {
//	            @Override public int compare(Pair p1, Pair p2)
//	            {
//	                return (int) (p1.a - p2.a);
//	            }
//	        });
//	  
//	    }
	public static long bs(ArrayList<Long> arr, long x , int l , long r) {
		
		while(l<=r) {
		int m = (int) ((l+r)/2);
		if(arr.get(m)>=x) {
			r = m-1;
		}else {
			l = m+1;
		}
		}
		return l;
		
	}
	public static long gs(ArrayList<Long> arr, long x , long l , long r) {
		
		while(l<=r) {
		int m = (int) ((l+r)/2);
		if(arr.get(m)<=x) {
			r = m+1;
		}else {
			l = m-1;
		}
		}
		return r;
		
	}
	 public static HashMap<Integer, Integer>
	    insertPF(HashMap<Integer, Integer> primeFact,
	             long fact)
	    {
	        if (primeFact.containsKey(fact)) {
	 
	            int freq;
	            freq = primeFact.get(fact);
	            primeFact.replace((int) fact, ++freq);
	        }
	        else {
	            primeFact.put((int) fact, 1);
	        }
	        return primeFact;
	    }
	 
	    // A utility function to find all
	    // prime factors of a given number N
	    public static HashMap<Integer, Integer>
	    primeFactors(long n)
	    {
	 
	        HashMap<Integer, Integer> primeFact
	            = new HashMap<>();
	 
	        // Insert the number of 2s
	        // that divide n
	        while (n % 2 == 0) {
	            primeFact = insertPF(primeFact, 2);
	            n /= 2;
	        }
	 
	        // n must be odd at this point.
	        // So we can skip one element
	        for (int i = 3; i <= Math.sqrt(n);
	             i += 2) {
	 
	            // While i divides n, insert i
	            // and divide n
	            while (n % i == 0) {
	                primeFact = insertPF(primeFact, i);
	                n /= i;
	            }
	        }
	 
	        // This condition is to handle
	        // the case when n is a prime
	        // number greater than 2
	        if (n > 2)
	            primeFact = insertPF(primeFact, n);
	 
	        return primeFact;
	    }
	 
	    // Function to check if a number
	    // is a perfect cube
	    public static boolean perfectCube(long n)
	    {
	 
	        HashMap<Integer, Integer> primeFact;
	        primeFact = primeFactors(n);
	 
	        // Using values() for iteration
	        // over keys
	        for (int freq : primeFact.values()) {
	            if (freq % 3 != 0)
	                return false;
	        }
	        return true;
	    }
	static String fixthisstring(String p,int n) {
		StringBuilder sb=new StringBuilder(p);
		if(p.length()>2) {
		for(int i=0;i<sb.length();i++) {
			
			if(i==0&& sb.charAt(i)=='?') {
				if(sb.charAt(i+1)=='0') {
					sb.setCharAt(i,'1');
				}else if(sb.charAt(i+1)=='1'){
					sb.setCharAt(i,'0');
				}else {
					if(sb.charAt(i+2)=='0') {
						sb.setCharAt(i,'0');
					}else if(sb.charAt(i+2)=='1') {
						sb.setCharAt(i,'1');
					}else {
						sb.setCharAt(i,'1');
					}
				}
			}else if(i==sb.length()-1 && sb.charAt(i)=='?') {
				if(sb.charAt(i-1)=='0') {
					sb.setCharAt(i,'1');
				}else {
					sb.setCharAt(i,'0');
				}
			}else if(sb.charAt(i)=='?'){
				if(sb.charAt(i+1)=='0') {
					
						sb.setCharAt(i,'1');
					
				}else if(sb.charAt(i+1)=='1'){
					sb.setCharAt(i,'0');
				}else if(sb.charAt(i+1)=='?') {
				
					if(sb.charAt(i-1)=='0') {
						sb.setCharAt(i,'1');
					}else {
						sb.setCharAt(i,'0');
					}
				}
			}
		}
		}else {
			if(p.contains("?") && p.length()==1) {
				return "0";
			}else if(p.contains("?")){
				return "01";
			}
		}
		return sb.toString();
		
	}
	 static void addEdge(ArrayList<ArrayList<Integer> > adj,
             int u, int v)
{
adj.get(u).add(v);
adj.get(v).add(u);
}

	static long binomialCoeff(long n, long l) {
        long res = 1;
        
        if (l > n - l) l = n - l;
        
        for (var i = 0; i < l; ++i) {
            res *= 1L*(n - i);
            res /= 1L*(i + 1);
        }
        
        return res;
    }
	static long nCr(long n, long r)
	{
	    return fact(n) / (fact(r) *
	                  fact(n - r));
	}
	static long fact(long n)
	{
	    long res = 1;
	    for (int i = 2; i <= n; i++)
	        res = res * i;
	    return res;
	}
	 

	static void  dfs(int m) {
		
		
		
		visit[m]=true;
		for(int i=0;i<adjList.get(m).size();i++) {
			int v=adjList.get(m).get(i);
			
			if(!visit[v]) {
				
				max++;
			 dfs(v);
			}
		}
		
		
	}
	static boolean dividetwothree(long n) {
		while(n!=1) {
			if(n%2==0) {
				n=n/2;
			}else if(n%3==0){
				n=n/3;
			}else {
				return false;
			}
			
			
		}
		return true;
	}
	static boolean isLuckyNumber(int n){
		while(n>0) {
			int y=n%10;
			n=n/10;
			if(y!=4 && y!=7) {
				return false;
			}
		}
		return true;
	}
	static boolean isInteger(double N)
	{
	 
	    // Convert float value
	    // of N to integer
	    long X = (long)N;
	    double temp2 = N - X;
	 
	    // If N is not equivalent
	    // to any integer
	    if (temp2 > 0)
	    {
	        return false;
	    }
	    return true;
	}
	static long isrecursive(long p) {
		if(p==0) {
			return 0;
		}else if(p%2==0) {
			return isrecursive(p/2);
		}else {
			return isrecursive(p/2)+1;
		}
		
	}
	static boolean islucky(long  r) {
		String temp = Long.toString(r);
		long[] newGuess = new long[temp.length()];
		long tu=0;
		boolean flag=false;
		
		for (int i = 0; i < temp.length(); i++)
		{
		    newGuess[i] = temp.charAt(i) - '0';
		    if(newGuess[i]==4 || newGuess[i]==7) {
		    	continue;
		    }else {
		    	flag=true;
		    	break;
		    }
		}
		if(flag) {
			return false;
		}
		return  true;
	}
	static int distance(long l,long m) {
		return (int) (Math.pow(l,2)+Math.pow(m,2));
	}
	static int findSmallest(int N)
	{
	  
	    // Base case
	    if (N == 0)
	        return 2;
	    if (N == 1)
	        return 1;
	  
	    int prime = N, counter = 0;
	    boolean found = false;
	  
	    // Loop continuously until isPrime returns
	    // true for a number greater than n
	    while (!found) {
	        if (isPrime(prime))
	            found = true;
	        else {
	  
	            // If the number is not a prime, then
	            // increment the number by 1 and the
	            // counter which stores the number
	            // to be added
	            prime++;
	            counter++;
	        }
	    }
	  
	    return counter;
	}
	static boolean isPrime(int n)
	{
	    // Base cases
	    if (n <= 1)
	        return false;
	    if (n <= 3)
	        return true;
	  
	    // This is checked so that we can skip
	    // middle five numbers in below loop
	    if (n % 2 == 0 || n % 3 == 0)
	        return false;
	  
	    // For all the remaining numbers, check if
	    // any number is a factor if the number
	    // or not
	    for (int i = 5; i * i <= n; i = i + 6)
	        if (n % i == 0 || n % (i + 2) == 0)
	            return false;
	  
	    // If none of the above numbers are the
	    // factors for the number, then the
	    // given number is prime
	    return true;
	}
	
	
		static int mod(int a, int m)
		{
		    return (a%m + m) % m;
		}
		
	static long getSum(long y)
    {
       long sum = 0;
 
        while (y != 0) {
            sum = sum + y % 10;
            y = y / 10;
        }
 
        return sum;
    }
	static boolean detect(int arr[],int x) {
		long sum=0;
		for(int i=0;i<arr.length;i++) {
			sum+=arr[i];
			if(sum==x) {
				return true;
			}
			
		}
		return false;
	}
	
    static class Node {
        String s;
        int val;
 
        public Node(String a, int v) {
            val = v;
            s = a;
        }
    }
	  
	 public static HashMap<Integer,Long> sortByValue(HashMap<Integer,Long> hm)
	    {
	        // Create a list from elements of HashMap
	        List<Map.Entry<Integer,Long> > list =
	               new LinkedList<Map.Entry<Integer,Long> >(hm.entrySet());
	 
	        // Sort the list
	        Collections.sort(list, new Comparator<Map.Entry<Integer,Long> >() {
				@Override
				public int compare(Entry<Integer,Long> o1, Entry<Integer,Long> o2) {
					return (int)-(o1.getValue()-o2.getValue());
				}
	        });
	         
	        // put data from sorted list to hashmap
	        HashMap<Integer,Long> temp = new LinkedHashMap<Integer,Long>();
	        for (Map.Entry<Integer,Long> aa : list) {
	            temp.put(aa.getKey(), aa.getValue());
	        }
	        return temp;
	    }
	
	 static long lcm(long a, long b)
	    {
	        return (a / gcd(a, b)) * b;
	    }
static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
	
	
//static void reduceFraction(int x, int y) 
//{ 
//    int d; 
//    d = gcd(x, y); 
//  
//    x = x / d; 
//    y = y / d; 
//  if(x>0 && y<0) {
//	  x=-x;
//	  y=-y;
//  }
//    System.out.println(y); 
//} 
	
	static long gcd(long a, long b) {
		return a%b == 0 ? b : gcd(b,a%b);
	}
	 static int getSum(int n)
	    {
	        int sum = 0;
	 
	        while (n != 0) {
	            sum = sum + n % 10;
	            n = n / 10;
	        }
	 
	        return sum;
	    }
	
	static boolean[] sieve(int n) {
		
		
		boolean isPrime[] = new boolean[n+1];
		for(int i = 2; i <= n; i++) {
			if(isPrime[i]) continue;
			for(int j = 2*i; j <= n; j+=i) {
				isPrime[j] = true;
			}
		
		} 
		return isPrime;
		
	}
	public static long SubString(String str, int n,long count)
	{
	for (int i = 0; i < n; i++) {
		for (int j = i+1; j <= n; j++) {
			
				String y=fixthisstring(str.substring(i, j),str.substring(i, j).length());
				
				if(y.length()==1) {
					count++;
				}else if(y.contains("00")||y.contains("11") ) {
					continue;
				}else {
					count++;
				}
		}
	}
	return count;
	}
    // Function to rearrange numbers in array such
    // that no two adjacent numbers are same
    static boolean rearrangeArray(int[] arr)
    {
        int n = arr.length;
 
        // Store frequencies of all elements
        // of the array
        int[] count = new int[10000];
        int visited[] = new int[10000];
 
        for (int i = 0; i < n; i++)
            count[arr[i]]++;
 
        // Insert all characters with their frequencies
        // into a priority_queue
        PriorityQueue<Key> pq
            = new PriorityQueue<>(new KeyComparator());
 
        // Adding high freq elements in descending order
        for (int i = 0; i < n; i++)
        {
            int val = arr[i];
 
            if (count[val] > 0 && visited[val] != 1)
                pq.add(new Key(count[val], val));
            visited[val] = 1;
        }
 
        // 'result[]' that will store resultant value
        int result[] = new int[n];
 
        // work as the previous visited element
        // initial previous element will be ( '-1' and
        // it's frequency will also be '-1' )
        Key prev = new Key(-1, -1);
 
        // Traverse queue
        int l = 0;
        while (pq.size() != 0)
        {
            // pop top element from queue and add it
            // to result
            Key k = pq.peek();
            pq.poll();
            result[l] = k.num;
 
            // If frequency of previous element is less
            // than zero that means it is useless, we
            // need not to push it
            if (prev.freq > 0)
                pq.add(prev);
 
            // make current element as the previous
            // decrease frequency by 'one'
            (k.freq)--;
            prev = k;
            l++;
        }
 
        // If length of the resultant array and original
        // array is not same then the array is not valid
        if (l != result.length)
        {
           return false;
        }
        // Otherwise Print the result array
        else
        	{int j=0;
            for (int i : result)
            {
                arr[j++]=i;
            }
            return true;
        }
    }
  
}
class KeyComparator implements Comparator<Key>
{
 
    // Overriding compare()method of Comparator
    public int compare(Key k1, Key k2)
    {
        if (k1.freq < k2.freq)
            return 1;
        else if (k1.freq > k2.freq)
            return -1;
        return 0;
    }
}
 
// Object of num and its freq
class Key
{
    int freq; // store frequency of character
    int num;
    Key(int freq, int num)
    {
        this.freq = freq;
        this.num = num;
    }
}
 class Pair {
    int a;
    int b;
    public Pair(int a, int b){
        this.a=a;
        this.b=b;
    }
}
class PairComparator implements Comparator<Pair>
{
 
    // Overriding compare()method of Comparator
    public int compare(Pair k1, Pair k2)
    {
      if(k1.a==k2.a) {
    	  if(k1.b>k2.b) {
    		  return 1;
    	  }else {
    		  return -1;
    	  }
      }else if(k1.a>k2.a) {
    	  return 1;
      }else {
    	  return -1;
      }
    }
}
 