#include
using namespace std;
typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int)
const int maxl = 103;
int bi[maxl], le; dint f[maxl], g[maxl][2];
dint digDP(dint n) { le = 0; for (; n; n »= 1, ++ le) bi[le] = n & 1; bi[le ++] = 0; memset(f, 0, sizeof(f)); memset(g, 0, sizeof(g)); g[0][0] = g[0][1] = 1; for (int i = 1; i < le; ++ i) { g[i][0] = g[i - 1][0] + g[i - 1][1]; g[i][1] = g[i - 1][0]; } f[0] = 1; for (int i = 1; i < le; ++ i) if (bi[i] == 1) { if (bi[i - 1] == 1) f[i] = g[i - 1][0]; else f[i] = f[i - 1]; } else { if (bi[i - 1] == 1) f[i] = f[i - 1] + g[i - 1][0]; else f[i] = f[i - 1]; } return f[le - 1] - 1; }
const int mod = 1e9 + 7; struct matrix { static const int n = 2; int a[n][n]; inline void clr() { memset(a, 0, sizeof(a)); } matrix() { clr(); } void setOne() { clr(); for (int i = 0; i < n; ++ i) a[i][i] = 1; } void mul(const matrix& b) { static int s[n][n]; memset(s, 0, sizeof(s)); for (int k = 0; k < n; ++ k) for (int i = 0; i < n; ++ i) for (int j = 0; j < n; ++ j) s[i][j] = (s[i][j] + _l a[i][k] * b. a[k][j]) % mod; memcpy(a, s, sizeof(a)); } };
int matDP(dint n) { matrix a, s; a. clr(); a. a[0][0] = a. a[0][1] = a. a[1][0] = 1; s. setOne(); for (; n; n »= 1, a. mul(a)) if (n & 1) s. mul(a); int ans((_l s. a[0][0] + s. a[0][1]) % mod); return ans; }
int main() { #ifdef LAEKOV_LOCAL freopen(".in", “r”, stdin); #endif
int t;
dint n;
scanf("%d", &t);
while (t --) {
scanf(lld, &n);
printf(lld "\n", digDP(n));
printf("%d\n", matDP(n));
}
}