#include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #define dbg(x) cerr << #x << " = " << x <<endl

 using namespace std;

 typedef long long ll;

 typedef double db;

 typedef pair<int,int> pii;

 template<typename T>inline T _min(T A,T B){return A<B?A:B;}

 template<typename T>inline T _max(T A,T B){return A>B?A:B;}

 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,):;}

 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,):;}

 template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}

 template<typename T>inline T read(T&x){

     x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;

     while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;

 }

 ll f[][];//mistake:long long

 int T,b[];

 ll n;//mistake:long long

 ll dp(int len,int las,int limit){

     if(!len)return ;

     if(!limit&&~f[len][las])return f[len][las];

     int num=limit?b[len]:;ll ret=;

     for(register int i=;i<=num;++i)

         ret+=las?(i?:dp(len-,,limit&&i==num)):dp(len-,i,limit&&i==num);

     return limit?ret:f[len][las]=ret;

 }

 inline ll task1(ll x){

     int len=;while(x)b[++len]=x&,x>>=;

     return dp(len,,)-;

 }

 const int P=1e9+;

 struct matrix{

     int a[][];

     matrix(){a[][]=a[][]=,a[][]=a[][]=;}

     inline void build(){a[][]=,a[][]=a[][]=a[][]=;}

     inline matrix operator *(const matrix&A)const{

         matrix B;

         B.a[][]=(a[][]*1ll*A.a[][]+a[][]*1ll*A.a[][])%P;

         B.a[][]=(a[][]*1ll*A.a[][]+a[][]*1ll*A.a[][])%P;

         B.a[][]=(a[][]*1ll*A.a[][]+a[][]*1ll*A.a[][])%P;

         B.a[][]=(a[][]*1ll*A.a[][]+a[][]*1ll*A.a[][])%P;

         return B;

     }

     inline void operator *=(const matrix&A){*this=*this * A;}

 };

 inline int task2(ll p){

     if(p==)return ;

     if(p==)return ;

     matrix ret,x;x.build();p-=;

     for(;p;p>>=,x*=x)if(p&)ret*=x;

     return (ret.a[][]*1ll*+ret.a[][]*1ll*)%P;

 }

 int main(){//freopen("test.in","r",stdin);freopen("test.ans","w",stdout);

     memset(f,-,sizeof f);

     read(T);while(T--)read(n),printf("%lld\n%d\n",task1(n),task2(n));

     return ;

 }