// Arup Guha
// Solution to 2008 Greater NY Regional Problem D: Recursively Palindromic Partitions

import java.util.*;

public class d {
	
	public static void main(String[] args) {
		
		Scanner stdin = new Scanner(System.in);
		
		// Use this array to store all the possible answers to the posed question.
		long answers[] = new long[1001];
		
		// Seed the table with these starting values.
		answers[0] = 0;
		answers[1] = 1;
		answers[2] = 2;
		
		// Loop through the rest of the values.
		for (int i=3; i<=1000; i++) {
			
			// This was the same recurrence relation you had derived.
			if (i%2 == 1)
				answers[i] = answers[i-1];
			else
				answers[i] = answers[i-2] + answers[i/2];
		}
		
		// Now process each case.
		int numCases = stdin.nextInt();
		
		for (int i=1; i<=numCases; i++) {
			int n = stdin.nextInt();
			System.out.println(i+" "+answers[n]);
		}
		
	}
}