#include #include #include #include #include #include #include #include #include #include #include #include<ext/pb_ds/priority_queue.hpp> using namespace std;

const int maxn = 20; const int p = 100000000;

struct data{ int len,a[maxn]; data(){len = 0; memset(a,0,sizeof(a));} data operator + (const data &b) { data c; int L = max(len,b.len); for (int i = 0; i < L; i++) { c.a[i] += a[i] + b.a[i]; c.a[i+1] += c.a[i] / p; c.a[i] %= p; } c.len = c.a[L]?L+1:L; return c; } data operator * (const data &b) { data c; for (int i = 0; i < len; i++) for (int j = 0; j < b.len; j++) { c.a[i+j] += a[i]b.a[j]; c.a[i+j+1] += c.a[i+j] / p; c.a[i+j] %= p; } c.len = c.a[len+b.len-1]?len+b.len:len+b.len-1; return c; } data operator / (const int &b) { data c; int res = 0; for (int i = len-1; i >= 0; i--) { c.a[i] = (a[i] + resp) / b; res = (a[i] + res*p) % b; } c.len = c.a[len-1]?len:len-1; return c; } bool operator == (const data &b) const { if (len != b.len) return 0; for (int i = len - 1; i >= 0; i--) if (a[i] != b.a[i]) return 0; return 1; } bool operator != (const data &b) const { if (len != b.len) return 1; for (int i = len - 1; i >= 0; i--) if (a[i] != b.a[i]) return 1; return 0; } }X,Y,Z;

int T; char ch[233];

void Get(data &g) { scanf("%s",ch + 1); int len = strlen(ch + 1),cnt = 0,now = 1,sum; for (int i = len; i; i--) { sum += now*(ch[i]-'0'); now *= 10; ++cnt; if (cnt == 8) { g.a[g.len++] = sum; cnt = sum = 0; now = 1; } } if (cnt) g.a[g.len++] = sum; }

data Solve(data A,data B,data ta,data tb) { if (A == Y && (B == X || B == Z)) { data ret; if (A == Y) ret = ret + ta; if (B == Z) ret = ret + tb; return ret; } data NA = X,NB = X,na = X,nb = X,g; if (A != X) { g = A / 2; na = na + ta; nb = nb + ta; if (g.a[0]&1) NA = g,NB = g + Y; else NB = g,NA = g + Y; } if (B != X) { g = B / 2; if (g.a[0]&1) na = na + tb,NA = g; else nb = nb + tb,NB = g; } return Solve(NA,NB,na,nb); }

void Print(int x,int res) { if (res == 1) {putchar(x + '0'); return;} Print(x/10,res-1); putchar(x%10 + '0'); }

int main() { #ifdef DMC freopen("DMC.txt","r",stdin); #endif

cin >> T; X.len = 1; 
Y.a[0] = 1; Y.len = 1;
Z.a[0] = 2; Z.len = 1;
while (T--)
{
	data g,f; Get(g);
	if (g == X) {puts("0"); continue;}
	f = (g.a[0]&1)?Solve(g,X,Y,X):Solve(X,g,X,Y);
	printf("%d",f.a[f.len-1]);
	for (int i = f.len - 2; i >= 0; i--) Print(f.a[i],8);
	puts("");
}
return 0;

}