import java.util.*;


public class palindrome {
	static Scanner in;
	static palindrome myPal;
	static Map<Integer,Integer> myMap;
	public static void main(String[] args){
		myMap=new HashMap<Integer,Integer>();
		myMap.put(1, 1);//base case
		myMap.put(0, 1);//base case
		myPal=new palindrome();
		int numData;
		
		in=new Scanner(System.in);
		numData=Integer.parseInt(in.nextLine());
		
		for (int k=0;k<numData;k++){
			int data= Integer.parseInt(in.nextLine());
			
			System.out.println((k+1) + " " + myPal.recurse(data));
		
		}
	}
	
	public int recurse(int num){
		if (myMap.containsKey(num)) return myMap.get(num);
		
		if (num%2==0){
			int tempAns=0;
			for (int k=0;k<=num;k+=2){
				tempAns+=recurse((num-k)/2);
			}
			myMap.put(num, tempAns);
			return tempAns;
		}
		else {
			int tempAns=0;//counting itself(would be when k below=num but stop before that to avoid recurse(0)
			for (int k=1;k<=num;k+=2){
				tempAns+=recurse((num-k)/2);
			}
			myMap.put(num, tempAns);
			return tempAns;//for
		}
	}
}