MAXARR1.cpp

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

int main() {
    cin.tie(0)->sync_with_stdio(0);
    const int N = 100000;
    vector<int> a(N + 2);
    a[0] = 0;
    a[1] = 1;
    for (int i = 1; i * 2 <= N; i++) {
        a[i * 2] = a[i];
        a[i * 2 + 1] = a[i] + a[i + 1];
    }
    for (int i = 1; i <= N; i++) {
        a[i] = max(a[i], a[i - 1]);
    }
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        cout << a[n] << '\n';
    }
}