import java.util.*;
import java.io.*;

public class Recur {
	
	Scanner in = new Scanner(System.in);
	int max;
	int[] answers;
	
	public static void main(String[] args) {
		new Recur().solve();
	}
	
	public void solve() {
		
		//in = new Scanner("3\n4\n7\n20");
		
		answers = new int[2000];
		max = 1;
		answers[0] = 1;
		answers[1] = 1;
		int num_cases = Integer.parseInt(in.nextLine());
		
		
		for(int i=2; i<2000; i++) {
			answers[i] = 0;
		}
		
		for(int case_num = 1; case_num <= num_cases; case_num++) {
			
			int n = Integer.parseInt(in.nextLine());
			if(n > max) calcUpTo(n);
			
			System.out.println(case_num + " " + answers[n]);
		}
		
	}
	
	public void calcUpTo(int n) {
		
		for(int curr_n=max+1; curr_n<=n; curr_n++) {
			
			int curr_ans=0;
			for(int mid=curr_n%2; mid<=curr_n; mid += 2) {
				curr_ans += answers[(curr_n-mid)/2];
			}
			answers[curr_n] = curr_ans;
		}
		max = n;	// we now know up to n
		
	}
}