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.math.BigInteger;
										import java.sql.Array;
									    import java.util.ArrayList;
										import java.util.Arrays;
										import java.util.Collection;
										import java.util.Collections;
										import java.util.Comparator;
										import java.util.HashMap;
										import java.util.InputMismatchException;
										import java.util.Iterator;
										import java.util.LinkedHashSet;
										import java.util.LinkedList;
										import java.util.List;
										import java.util.Map;
										import java.util.Map.Entry;	
										import java.util.PriorityQueue;
										import java.util.Queue;
										import java.util.Scanner;
										import java.util.Set;
										import java.util.Stack;
										import java.io.BufferedReader;
										import java.io.IOException;
										import java.io.InputStream;
										import java.io.InputStreamReader;
										import java.util.Scanner;
										import java.util.StringTokenizer;
										import java.util.TreeMap;
										import java.util.TreeSet;
										
										
										
										public class Main {
											
										static long l[];	
										static int k;	
												
											static InputReader rd=new InputReader(System.in);
											public static void main(String[] args) {
												Scanner sc=new Scanner(System.in);
												
												int t=sc.nextInt();
												while(t-->0) {
														long n=sc.nextLong();
														
														long s=0;
														while(n>0) {
															//System.out.println(n+" "+s);
															if((n%2==0&&((n/2)%2!=0))||n==4) {
																s+=n/2;
																n=n/2;
																
															}
															else {
																s+=1;
																n--;
																
															}
															if((n%2==0&&((n/2)%2!=0))||n==4) {
																//sc+=n/2;
																n=n/2;
																
															}
															else {
																n--;
																
															}
															
															
															
														}
														System.out.println(s);
		
														}
														
														
														
														
													}
													
													
													
													
													
												
												
												
												
												
										
												
											static long power1(long x, long y, long p) 
										    { 
										        // Initialize result 
										        long res = 1;      
										         
										        // Update x if it is more   
										        // than or equal to p 
										        x = x % p;  
										  
										       if (x == 0) return 0; // In case x is divisible by p;    
										  
										        while (y > 0) 
										        { 
										            // If y is odd, multiply x 
										            // with result 
										            if((y & 1)==1) 
										                res = (res * x) % p; 
										      
										            // y must be even now 
										            // y = y / 2 
										            y = y >> 1;  
										            x = (x * x) % p;  
										        } 
										        return res; 
										    } 	
								static void dfs(ArrayList<ArrayList<graph>> g,int v,boolean visited[]) {
									
									visited[v]=true;
									l[k]+=1;
									for(graph j:g.get(v)) {
										if(j.c==0) {
											//System.out.println(v);
											if(!visited[j.v])
											dfs(g,j.v,visited);
										}
										
									}
									
									
								}
											
											
								static class graph{
									int v;int c;
									public graph(int v,int c) {
										// TODO Auto-generated constructor stub
										this.v=v;
										this.c=c;
									
									}
									
								}
											
											
												
											
									static		long fact(long n) {
												
												if(n<=1)return 1;
												else return n*fact(n-1);
											}
											
							 static long maxCrossingSum(long arr[], int l, 
						                                int m, int h) 
						    { 
						        // Include elements on left of mid. 
						       long sum = 0; 
						        long left_sum = Integer.MIN_VALUE; 
						        for (int i = m; i >= l; i--) 
						        { 
						            sum = sum + arr[i]; 
						            if (sum > left_sum) 
						            left_sum = sum; 
						        } 
						  
						        // Include elements on right of mid 
						        sum = 0; 
						        long right_sum = Integer.MIN_VALUE; 
						        for (int i = m + 1; i <= h; i++) 
						        { 
						            sum = sum + arr[i]; 
						            if (sum > right_sum) 
						            right_sum = sum; 
						        } 
						  
						        // Return sum of elements on left 
						        // and right of mid 
						       // returning only left_sum + right_sum will fail for [-2, 1] 
						        return Math.max(left_sum + right_sum, Math.max(left_sum, right_sum)); 
						    } 
						  
						    // Returns sum of maxium sum subarray  
						    // in aa[l..h] 
						    static long maxSubArraySum(long arr[], int l,  
						                                      int h) 
						    { 
						    // Base Case: Only one element 
						    if (l == h) 
						        return arr[l]; 
						  
						    // Find middle point 
						    int m = (l + h)/2; 
						  
						    /* Return maximum of following three  
						    possible cases: 
						    a) Maximum subarray sum in left half 
						    b) Maximum subarray sum in right half 
						    c) Maximum subarray sum such that the  
						    subarray crosses the midpoint */
						    return Math.max(Math.max(maxSubArraySum(arr, l, m), 
						                    maxSubArraySum(arr, m+1, h)), 
						                    maxCrossingSum(arr, l, m, h)); 
						    } 
											
											static long abs(long a) {
												return Math.abs(a);
											}
											
											static class seg{
												
												int x;int y;int l;
												public seg(int x,int y,int l) {
													this.x=x;
													this.y=y;
													this.l=l;
													// TODO Auto-generated constructor stub
												}
												
												
											}
										static	boolean isPresent(int j,int p) {
												
												int i=(j/50)%475;
												
												for(int k=0;k<25;k++) {
												    i = (i * 96 + 42)% 475;
												    if(26+i==p)return true;
													}
												return false;
												
											}
																			
											static class Helper{
												int val;int index;
												public Helper(int  val,int index) {
													
													this.val=val;
													this.index=index;
													// TODO Auto-generated constructor stub
												}
											}
										
									
											
							
										    static boolean isPrime(int n) 
										    { 
										        // Corner 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 (int i = 5; i * i <= n; i = i + 6) 
										            if (n % i == 0 || n % (i + 2) == 0) 
										                return false; 
										  
										        return true; 
										    } 
									
											      
											    /* Iterative Function to calculate 
											       (x^y)%p in O(log y) */
											    static long power(long x, long y, long p) 
											    { 
											        // Initialize result 
											        long res = 1;      
											         
											        // Update x if it is more   
											        // than or equal to p 
											        x = x % p;  
											  
											       if (x == 0) return 0; // In case x is divisible by p;    
											  
											        while (y > 0) 
											        { 
											            // If y is odd, multiply x 
											            // with result 
											            if((y & 1)==1) 
											                res = (res * x) % p; 
											      
											            // y must be even now 
											            // y = y / 2 
											            y = y >> 1;  
											            x = (x * x) % p;  
											        } 
											        return res; 
											    } 
								
											
											
											
											  static class InputReader {
											        private InputStream stream;
											        private byte[] buf = new byte[1024];
											        private int curChar;
											        private int numChars;
											        private SpaceCharFilter filter;
										
											        public InputReader(InputStream stream) {
											            this.stream = stream;
											        }
										
											        public int read() {
											            if (numChars == -1)
											                throw new InputMismatchException();
											            if (curChar >= numChars) {
											                curChar = 0;
											                try {
											                    numChars = stream.read(buf);
											                } catch (IOException e) {
											                    throw new InputMismatchException();
											                }
											                if (numChars <= 0)
											                    return -1;
											            }
											            return buf[curChar++];
											        }
										
											        public int readInt() {
											            int c = read();
											            while (isSpaceChar(c))
											                c = read();
											            int sgn = 1;
											            if (c == '-') {
										    sgn = -1;
										    c = read();
										}
										int res = 0;
										do {
										    if (c < '0' || c > '9')
										        throw new InputMismatchException();
										    res *= 10;
										    res += c - '0';
										        c = read();
										    } while (!isSpaceChar(c));
										    return res * sgn;
										}
										
										public String readString() {
										    int c = read();
										    while (isSpaceChar(c))
										        c = read();
										    StringBuilder res = new StringBuilder();
										    do {
										        res.appendCodePoint(c);
										        c = read();
										    } while (!isSpaceChar(c));
										    return res.toString();
										}
										
										public boolean isSpaceChar(int c) {
										    if (filter != null)
										        return filter.isSpaceChar(c);
										    return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
											        }
										
											        public String next() {
											            return readString();
											        }
										
											    }
											
											  public interface SpaceCharFilter {
											        public boolean isSpaceChar(int ch);
											    }	
											
											
																				
																				
																				
																	
										}
										    