Lately, Mr. Chanek frequently plays the game Arena of Greed. As the name implies, the game's goal is to find the greediest of them all, who will then be crowned king of Compfestnesia.

The game is played by two people taking turns, where Mr. Chanek takes the first turn. Initially, there is a treasure chest containing N gold coins. The game ends if there are no more gold coins in the chest. In each turn, the players can make one of the following moves:

  * Take one gold coin from the chest. 
  * Take half of the gold coins on the chest. This move is only available if the number of coins in the chest is even. 



Both players will try to maximize the number of coins they have. Mr. Chanek asks your help to find the maximum number of coins he can get at the end of the game if both he and the opponent plays optimally.

Input

The first line contains a single integer T (1 ≤ T ≤ 10^5) denotes the number of test cases.

The next T lines each contain a single integer N (1 ≤ N ≤ 10^{18}).

Output

T lines, each line is the answer requested by Mr. Chanek.

Example

Input


2
5
6


Output


2
4

Note

For the first case, the game is as follows: 

  1. Mr. Chanek takes one coin. 
  2. The opponent takes two coins. 
  3. Mr. Chanek takes one coin. 
  4. The opponent takes one coin. 



For the second case, the game is as follows: 

  1. Mr. Chanek takes three coins. 
  2. The opponent takes one coin. 
  3. Mr. Chanek takes one coin. 
  4. The opponent takes one coin. 
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
import java.util.Arrays;
import java.util.ArrayList;
import java.lang.Math; 
import java.util.Arrays;
import java.util.Comparator;
 
 
 
public class Main 
{ 
    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 int binarySearch(int a[] ,int k,int l,int h){
        
        while(l<=h){
         int mid = (l+h)/2;
         if(a[mid]==k) return mid;
         else if(a[mid]>k) h=mid-1;
         else if(a[mid]<k) l=mid+1;
        }
        
        return -1;
    }

    static int binarySearch(ArrayList<Integer> a ,int k,int l,int h){
        
        while(l<=h){
         int mid = (l+h)/2;
         if(a.get(mid)==k) return mid;
         else if(a.get(mid)>k) h=mid-1;
         else if(a.get(mid)<k) l=mid+1;
        }
        
        return -1;
    }

    static String reverse(String input)  
    { 
        char[] a = input.toCharArray(); 
        int l, r = 0; 
        r = a.length - 1; 
  
        for (l = 0; l < r; l++, r--) 
        { 
            // Swap values of l and r  
            char temp = a[l]; 
            a[l] = a[r]; 
            a[r] = temp; 
        } 
        return String.valueOf(a); 
    } 

   
    
    static int gcd(int a, int b) 
    { 
        // Everything divides 0  
        if (a == 0) 
          return b; 
        if (b == 0) 
          return a; 
       if (a == b) 
            return a; 
       if (a > b) 
            return gcd(a-b, b); 
        return gcd(a, b-a); 
    } 

    static int lcm(int a, int b) 
    { 
        return (a*b)/gcd(a, b); 
    } 

    static int solve(int A, int B) 
    { 
    int count = 0; 
    for (int i = 0; i < 21; i++) { 
        if (((A >> i) & 1) != ((B >> i) & 1)) { 
            count++; 
        } 
     } 
  
      return count;
    } 

    static long nCr(int n, int r) 
    { 
    return fact(n) / (fact(r) * 
    fact(n - r)); 
    } 
        
        
    static long fact(int n) 
    { 
    long res = 1; 
    for (int i = 2; i <= n; i++) 
    res = res * i; 
    return res; 
    } 
        
    public static long count(long k) {
    return k * (k - 1) / 2;
    }

    static boolean isPrime(int n) { 
            // if(n==1) return false; 
    if(n==2) return true;
    if (n%2==0) return false; 
    
    int l = (int)Math.sqrt(n);
    for(int i=3;i<=l;i+=2) { 
        if(n%i==0) 
        return false; 
    } 
    return true; 
    }

    static int negMod(int n){
    int a = (n % 1000000007 + 1000000007) % 1000000007;
    return a;
    }
        

    public static int sum(long x) {
    int sum = 0;
    while (x > 0) {
    sum += x % 10;
    x /= 10;
    }
    return sum;
    }
    

    public static int max(int x, int y, int z)
    {
        return (int)Math.max(Math.max(x, y), z);
    }
    
    
    public static int min(int x, int y, int z)
    {
        return (int)Math.min(Math.min(x, y), z);
    }
    
    

   static  void  bipartite(int n,int c,int color[]){
     visited[n] = 1;
     color[n] = c;
     
     Iterator<Integer> i = adj.get(n).listIterator(); 
        while (i.hasNext()) 
        { 
            int a = i.next(); 
            if (visited[a]==0) 
            bipartite(a,c^1,color); 
        } 
   }
   
    static double distance(int x,int y,int r1,int r2){
        double ans = Math.sqrt((x-r1)*(x-r1) + (y-r2)*(y-r2));
        return ans;
    }  
    
        
    
    static ArrayList<ArrayList<Integer>> adj = new  ArrayList<ArrayList<Integer>>();
    static int visited[] = new int[100002];

    static void addEdge(int u, int v) 
        { 
        adj.get(u).add(v); 
        adj.get(v).add(u); 
        } 

    static void dfs(int a){
            visited[a] = 1;
            
            Iterator<Integer> i = adj.get(a).listIterator(); 
            
             while (i.hasNext()) 
             { 
                 int n = i.next(); 
                 if (visited[n]==0) {
                     
                     dfs(n); 
                 }
                    
             }
             
    }
    
    static boolean dfscycle(int node , int parent){
           visited[node] = 1;
           
          
           Iterator<Integer> i = adj.get(node).listIterator(); 
            
             while (i.hasNext()) 
             { 
                 int n = i.next(); 
                 if (visited[n]==0) {
                     
                    if(dfscycle(n,node) == true) return true;
                 }
                 else if(n!=parent) return true;
                 
             }

         return false;
    }

    static int mod=1000003;
    static long m=1073741824;
    
    static ArrayList<Long> divisors(long n) 
    { 
        ArrayList<Long> a = new   ArrayList<Long>();
        int count = 0;
        for (long i=1; i<=Math.sqrt(n); i++) 
        { 
            if (n%i==0) 
            { 
                
                if (n/i == i) 
                    a.add(i);
       
                else // Otherwise print both 
                    {
                        a.add(i);
                        a.add(n/i);
                    }
            } 
        } 
        return a;
    } 
    
    
    public static void main(String[] args) throws Exception 
    {   
        
        OutputStream outputStream = System.out;
        FastReader sc = new FastReader();
        PrintWriter w = new PrintWriter(outputStream);
        // Scanner sc = new Scanner(new File("input.txt"));
        // PrintWriter out = new PrintWriter(new File("output.txt"));

        int i,j=0;
        
        // int t = 1;
        int t = sc.nextInt();
        
        while(t>0){
           
        long n = sc.nextLong();
        long ans = 0;
        j=0;
        while(n>0){
        
            if(j==0){
                if((n%2==0 && (n/2)%2!=0) || n==4){
                  ans += n/2;
                  n = n/2;
                  j=1;
                }
                else{
                    ans+=1;
                    n-=1;
                    j=1;
                }
            }
            else{
                if((n%2==0 && (n/2)%2!=0) || n==4){
                   
                    n = n/2;
                    j=0;
                  }
                  else{
                      
                      n-=1;
                      j=0;
                  } 
            }
        }
        w.println(ans);
        t--;
        }
        w.close();
    }
    
    
   
     
           
}
        
        
    

       




// System.out.println();

        
    
    

