#include <bits/stdc++.h>
using namespace std;

int main() {
	long long n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		if (x == 0) {
			cout << 0 << endl;
		}
		if (x == 1) {
			cout << 1 << endl;
		}
		if (x == 2) {
			cout << 1 << endl;
		}
		if (x == 3) {
			cout << 2 << endl;
		}
		if (x == 4) {
			cout << 3 << endl;
		}
		if (x == 5) {
			cout << 5 << endl;
		}
		if (x == 6) {
			cout << 8 << endl;
		}
		if (x == 7) {
			cout << 13 << endl;
		}
		if (x == 8) {
			cout << 21 << endl;
		}
		if (x == 9) {
			cout << 34 << endl;
		}
		if (x == 10) {
			cout << 55 << endl;
		}
		if (x == 11) {
			cout << 89 << endl;
		}
		if (x == 12) {
			cout << 144 << endl;
		}
		if (x == 13) {
			cout << 233 << endl;
		}
		if (x == 14) {
			cout << 377 << endl;
		}
		if (x == 15) {
			cout << 610 << endl;
		}
		if (x == 16) {
			cout << 987 << endl;
		}
		if (x == 17) {
			cout << 1597 << endl;
		}
		if (x == 18) {
			cout << 2584 << endl;
		}
		if (x == 19) {
			cout << 4181 << endl;
		}
		if (x == 20) {
			cout << 6765 << endl;
		}
		if (x == 21) {
			cout << 10946 << endl;
		}
		if (x == 22) {
			cout << 17711 << endl;
		}
		if (x == 23) {
			cout << 28657 << endl;
		}
		if (x == 24) {
			cout << 46368 << endl;
		}
		if (x == 25) {
			cout << 75025 << endl;
		}
		if (x == 26) {
			cout << 121393 << endl;
		}
		if (x == 27) {
			cout << 196418 << endl;
		}
		if (x == 28) {
			cout << 317811 << endl;
		}
		if (x == 29) {
			cout << 514229 << endl;
		}
		if (x == 30) {
			cout << 832040 << endl;
		}
		if (x == 31) {
			cout << 1346269 << endl;
		}
	}

	return 0;
}