#include<iostream>
using namespace std;

const int MAX = 2140000000;
int f[1000001];

void Dfs(int p)
{
    int i,sum = 1,temp;
    if(p % 2 == 1)
    {
        for(i = 1; i < p;i+=2)
        {
            temp = (p - i)/2;
            if(f[temp] == MAX)
                Dfs(temp);
            sum += f[temp];
        }
    }
    else
    {
        for(i = 0;i < p;i+=2)
        {
            temp = (p - i)/2;
            if(f[temp] == MAX)
                Dfs(temp);
            sum += f[temp];
        }
    }
    f[p] = sum;
}

int main()
{
    int text;
    cin>>text;
    int i;
    for(i = 0;i <= 1000000;i++)
        f[i] = MAX;
    int cases = 1;    
    f[0] = 0;
    f[1] = 1;
    f[2] = 2;
    f[3] = 2;
    f[4] = 4;
    while(text--)
    {
        int n;
        cin>>n;
        if(f[n] == MAX)
            Dfs(n);        
        cout<<cases++<<" "<<f[n]<<endl;
    }
    return 0;
}