#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  int flag = 1;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (x % 2 == 0) {
      cout << x / 2 << '\n';
    } else {
      cout << (x + flag) / 2 << '\n';
      flag *= -1;
    }
  }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    --a[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> b[i];
    --b[i];
  }
  vector<int> pos(n);
  for (int i = 0; i < n; i++) {
    pos[b[i]] = i;
  }
  vector<int> c(n);
  for (int i = 0; i < n; i++) {
    c[i] = pos[a[i]];
  }
  int mx = -1, ans = 0;
  for (int i = 0; i < n; i++) {
    if (c[i] > mx) {
      mx = c[i];
    } else {
      ++ans;
    }
  }
  cout << ans << '\n';
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<pair<int, int>, pair<int, int> > ii;

int main(){
    int n;
    cin >> n;
    
    vector<ii> v(n);
    for (int i = 0; i < n; i++){
        cin >> v[i].first.first >> v[i].first.second >> v[i].second.first;
        v[i].second.second = i + 1;
    }
    
    while(!v.empty()){
        sort(v.begin(), v.end());
        int x = v.back().first.first;
        int y = v.back().first.second;
        int z = v.back().second.first;
        int pos = v.back().second.second;
        v.pop_back();
        int ind = 0;
        ll d = 1e10;
        for (int i = 0; i < (int) v.size(); i++){
            ll dist = abs(v[i].first.first - x);
            dist += abs(v[i].first.second - y);
            dist += abs(v[i].second.first - z);
            if (dist < d){
                d = dist;
                ind = i;
            }
        }
        cout << pos << " " << v[ind].second.second << endl;
        v.erase(v.begin() + ind);
    }
}

#include <bits/stdc++.h>

using namespace std;

const int D = 3;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<vector<int>> p(n, vector<int>(D));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < D; j++) {
      cin >> p[i][j];
    }
  }
  auto Solve = [&](auto& Self, vector<int> ids, int k) {
    if (k == D) {
      return ids[0];
    }
    map<int, vector<int>> mp;
    for (int x : ids) {
      mp[p[x][k]].push_back(x);
    }
    vector<int> a;
    for (auto& q : mp) {
      int cur = Self(Self, q.second, k + 1);
      if (cur != -1) {
        a.push_back(cur);
      }
    }
    for (int i = 0; i + 1 < (int) a.size(); i += 2) {
      cout << a[i] + 1 << " " << a[i + 1] + 1 << '\n';
    }
    return (a.size() % 2 == 1 ? a.back() : -1);
  };
  vector<int> t(n);
  iota(t.begin(), t.end(), 0);
  Solve(Solve, t, 0);
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(3 * n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    a[i + n] = a[i + 2 * n] = a[i];
  }
  vector<int> ans(3 * n);
  vector<int> st_max;
  vector<int> st_min;
  for (int i = 3 * n - 1; i >= 0; i--) {
    while (!st_max.empty() && a[st_max.back()] < a[i]) {
      st_max.pop_back();
    }
    while (!st_min.empty() && a[st_min.back()] > a[i]) {
      st_min.pop_back();
    }
    int low = 0, high = (int) st_min.size();
    while (low < high) {
      int mid = (low + high) >> 1;
      if (a[st_min[mid]] * 2 < a[i]) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }
    int nxt = 3 * n;
    if (low > 0) {
      nxt = min(nxt, st_min[low - 1]);
    }
    if (!st_max.empty()) {
      nxt = min(nxt, st_max.back());
    }
    if (nxt < 3 * n && a[nxt] >= a[i]) {
      ans[i] = ans[nxt];
    } else {
      ans[i] = nxt;
    }
    st_min.push_back(i);
    st_max.push_back(i);
  }
  for (int i = 0; i < n; i++) {
    if (i > 0) {
      cout << " ";
    }
    cout << (ans[i] == 3 * n ? -1 : ans[i] - i);
  }
  cout << '\n';
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  int x = 1;
  while (x <= n) {
    if (n == x || n == x + 1) {
      cout << 1 << '\n';
      return 0;
    }
    if (x % 2 == 0) {
      x = x + 1 + x;
    } else {
      x = (x + 1) + 1 + x;
    }
  }
  cout << 0 << '\n';
  return 0;
}

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

const int MOD = 998244353;
const int MAX = 3610;
ll dp1[MAX][MAX], dp2[MAX][MAX];
int has1[MAX], has2[MAX];
ll fac[MAX], c[MAX][MAX];
int n, m, k;

void make(int n){
    dp1[0][0] = 1;
    for (int i = 1; i <= n; i++){
        for (int j = 0; j <= m; j++){
            dp1[i][j] = dp1[i - 1][j];
            if (j && i >= 2 && has1[i] == 0 && has1[i - 1] == 0){
                dp1[i][j] += dp1[i - 2][j - 1];
            }
            dp1[i][j] %= MOD;
        }
    }
}

int main(){
    cin >> n >> m >> k;
    int t = max(n, m) + 1;
    vector<ll> f(t);
    for (int i = 1; i <= k; i++){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        if (has1[a] || has1[c] || has2[b] || has2[d]){
            cout << 0 << endl;
            return 0;
        }
        has1[a] = has1[c] = has2[b] = has2[d] = 1;
    }
    int N = n, M = m;
    for (int i = 1; i <= n; i++){
        N -= has1[i];
    }
    for (int i = 1; i <= m; i++){
        M -= has2[i];
    }
    make(n);
    swap(dp1, dp2);
    swap(has1, has2);
    make(m);
    swap(dp1, dp2);
    swap(has1, has2);
    c[0][0] = 1;
    f[0] = 1;
    for (int i = 1; i < t; i++){
        f[i] = (f[i - 1] * i) % MOD;
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; j++){
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
            if (c[i][j] >= MOD){
                c[i][j] -= MOD;
            }
        }
    }
    ll ans = 0;
    for (int i = 0; (i << 1) <= N; i++){
        for (int j = 0; (j << 1) <= M; j++){
            int have1 = N - 2 * i;
            int have2 = M - 2 * j;
            ll res = dp1[n][i] * dp2[m][j];
            res %= MOD;
            res *= c[have1][j];
            res %= MOD;
            res *= c[have2][i];
            res %= MOD;
            res *= f[i];
            res %= MOD;
            res *= f[j];
            res %= MOD;
            ans += res;
        }
    }
    ans %= MOD;
    cout << ans << endl;
}

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

const int maxn = 200005;
const int maxk = 19;
const int inf = 1e9;

ll a[2 * maxn];
ll psum[2 * maxn];
pair2<int> go[maxk][2 * maxn];
map<ll, int> lst[maxn];
int id[2 * maxn];
int n, k;
ll need;
vector<pair<int, vector<ll>>> answer;

void perform(int l)
{
    int fn = min(l + k, n);
    assert(psum[fn] >= 0);
    ll wassum = psum[fn];
    vector<ll> exchange = vector<ll>(k, need);
    int start = min(n - k, l);
    for (int i = start; i < l; i++) exchange[i - start] = need + a[i];
    exchange[l - start] += -psum[l];
    exchange.back() += psum[fn];
    answer.pb({start, exchange});
    for (int i = l; i < fn; i++) a[i] = 0;
    a[l] += -psum[l];
    a[fn - 1] += psum[fn];
    for (int i = start; i < start + k; i++) psum[i + 1] = psum[i] + a[i];
    assert(wassum == psum[fn]);
}

void restore(int l)
{
    if (l >= n) return;
    if (a[l] == 0 && psum[l] == 0)
    {
        restore(l + 1);
        return;
    }
    int fn = min(l + k, n);
    if (psum[fn] >= 0)
    {
        perform(l);
        restore(l + k - (psum[fn] > 0));
        return;
    } else
    {
        restore(l + k - 1);
        assert(psum[fn] == 0);
        perform(l);
    }
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
    need = accumulate(a, a + n, 0LL);
    assert(need % n == 0);
    need /= n;
    for (int i = 0; i < n; i++) a[i] -= need;
    for (int i = 0; i < n; i++) a[i + n] = a[i];
    partial_sum(a, a + 2 * n, psum + 1);
    pair2<int> ans = {inf, -1};
    for (int j = 0; j < maxk; j++) go[j][2 * n] = {2 * n, 0};
    for (int i = 2 * n - 1; i >= 0; i--)
    {
        int curid = id[i + 1];
        if (lst[curid].count(psum[i]))
        {
            int to = lst[curid][psum[i]];
            go[0][i] = {to, (to - i - 1) / (k - 1)};
        } else
        {
            int to = 2 * n;
            go[0][i] = {to, (to - i + k - 2) / (k - 1)};
        }
        for (int j = 1; j < maxk; j++) go[j][i] = {go[j - 1][go[j - 1][i].fi].fi, go[j - 1][i].se + go[j - 1][go[j - 1][i].fi].se};
        
        if (i < n)
        {
            int to = n + i;
            int cur = i;
            int curans = 0;
            for (int j = maxk - 1; j >= 0; j--) if (go[j][cur].fi <= to)
            {
                curans += go[j][cur].se;
                cur = go[j][cur].fi;
            }
            if (cur < to) curans += (to - cur - 1 + k - 2) / (k - 1);
            ans = min(ans, {curans, i});
        }
        
        id[i] = (2 * n - i) % (k - 1);
        lst[id[i]][psum[i]] = i;
    }
    
    rotate(a, a + ans.se, a + n);
    partial_sum(a, a + n, psum + 1);
    restore(0);
    
    assert((int)answer.size() == ans.fi);
    printf("%d\n", (int)answer.size());
    for (auto &t : answer)
    {
        printf("%d", (t.fi + ans.se) % n);
        for (auto tt : t.se) printf(" %lld", tt);
        printf("\n");
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

const int maxn = 4005;

vector<int> ss, tt;
char s[maxn], t[maxn];
int n;
vector<int> answer;
int cnt[5];

vector<int> prepare(char *s)
{
    vector<int> ans;
    for (int i = 0; i < 2 * n; i += 2) ans.pb((s[i] - '0') * 2 + (s[i + 1] - '0'));
    return ans;
}

inline void addanswer(int x)
{
    if (x <= 0) return;
    answer.pb(x);
}

void doreverse(vector<int> &v, int l)
{
    reverse(v.begin(), v.begin() + l);
    for (int j = 0; j < l; j++) if (v[j] >= 1 && v[j] <= 2)
    {
        v[j] = 3 - v[j];
    }
}

int main()
{
    int NT;
    scanf("%d", &NT);
    for (int T = 0; T < NT; T++)
    {
        scanf("%s%s", s, t);
        n = strlen(s) / 2;
        ss = prepare(s);
        tt = prepare(t);
        for (auto &t : tt) if (t == 1 || t == 2) t = 3 - t;
        cnt[0] = cnt[1] = cnt[2] = cnt[3] = 0;
        for (auto t : ss) cnt[t]++;
        for (auto t : tt) cnt[t]--;
        if (cnt[0] != 0 || cnt[3] != 0)
        {
            printf("-1\n");
            continue;
        }
        bool found = cnt[1] == 0;
        int before = -1;
        int after = -1;
        for (int i = 1; i <= n && !found; i++)
        {
            cnt[ss[i - 1]]--;
            cnt[3 - ss[i - 1]]++;
            if (cnt[1] == 0)
            {
                before = 2 * i;
                doreverse(ss, i);
                found = true;
            }
        }
        if (!found)
        {
            for (int i = 1; i <= n; i++)
            {
                cnt[ss[i - 1]]++;
                cnt[3 - ss[i - 1]]--;
            }
        }
        for (int i = 1; i <= n && !found; i++)
        {
            cnt[tt[i - 1]]++;
            cnt[3 - tt[i - 1]]--;
            if (cnt[1] == 0)
            {
                after = 2 * i;
                doreverse(tt, i);
                found = true;
            }
        }
        assert(found);
        
        answer.clear();
        addanswer(before);
        for (int i = n - 1; i >= 0; i--)
        {
            int wh = -1;
            for (int j = n - 1 - i; j < n; j++) if (ss[j] == tt[i]) wh = j;
            addanswer(2 * wh);
            doreverse(ss, wh);
            addanswer(2 * wh + 2);
            doreverse(ss, wh + 1);
        }
        addanswer(after);
        
        for (auto t : answer) reverse(s, s + t);
        assert(strcmp(s, t) == 0);
        
        printf("%d ", (int)answer.size());
        for (auto t : answer) printf("%d ", t);
        printf("\n");
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  printf("%d\n", n >= 31 ? m : m % (1 << n));
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> p(n), deg(n);
  for (int i = 1; i < n; i++) {
    cin >> p[i];
    p[i]--;
    deg[p[i]]++;
  }
  vector<int> sons_leaves(n);
  for (int i = 0; i < n; i++) {
    if (deg[i] == 0) {
      sons_leaves[p[i]]++;
    }
  }
  for (int i = 0; i < n; i++) {
    if (deg[i] > 0 && sons_leaves[i] < 3) {
      puts("No");
      return 0;
    }
  }
  puts("Yes");
  return 0;
}

n = int(input())
p = [int(input()) - 1 for _ in range(n - 1)]
leafs = list(filter(lambda x: not x in p, range(n)))
lp = [x for i, x in enumerate(p) if i + 1 in leafs]
x = min(lp.count(k) for k in p)
print("Yes" if x >= 3 else "No")

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n, L;
  scanf("%d %d", &n, &L);
  vector<int> c(n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &c[i]);
  }
  for (int i = 0; i < n - 1; i++) {
    c[i + 1] = min(c[i + 1], 2 * c[i]);
  }
  long long ans = (long long) 4e18;
  long long sum = 0;
  for (int i = n - 1; i >= 0; i--) {
    int need = L / (1 << i);
    sum += (long long) need * c[i];
    L -= need << i;
    ans = min(ans, sum + (L > 0) * c[i]);
  }
  cout << ans << endl;
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n, T;
  scanf("%d %d", &n, &T);
  vector<int> a(n), t(n);
  for (int i = 0; i < n; i++) {
    scanf("%d %d", &a[i], &t[i]);
  }
  vector<int> res;
  int low = 0, high = n;
  while (low < high) {
    int mid = (low + high + 1) >> 1;
    vector< pair<int,int> > e;
    for (int i = 0; i < n; i++) {
      if (a[i] >= mid) {
        e.emplace_back(t[i], i);
      }
    }
    sort(e.begin(), e.end());
    bool ok = false;
    if ((int) e.size() >= mid) {
      int sum = 0;
      for (int i = 0; i < mid; i++) {
        sum += e[i].first;
      }
      if (sum <= T) {
        ok = true;
        res.resize(mid);
        for (int i = 0; i < mid; i++) {
          res[i] = e[i].second;
        }
      }
    }
    if (ok) {
      low = mid;
    } else {
      high = mid - 1;
    }
  }
  int sz = (int) res.size();
  printf("%d\n%d\n", sz, sz);
  for (int i = 0; i < sz; i++) {
    if (i > 0) {
      putchar(' ');
    }
    printf("%d", res[i] + 1);
  }
  printf("\n");
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n, T;
  scanf("%d %d", &n, &T);
  vector< vector< pair<int, int> > > at(n + 1);
  for (int i = 0; i < n; i++) {
    int foo, bar;
    scanf("%d %d", &foo, &bar);
    at[foo].emplace_back(bar, i);
  }
  vector<int> res;
  set< pair<int, int> > s;
  int sum = 0;
  for (int k = n; k > 0; k--) {
    for (auto &p : at[k]) {
      sum += p.first;
      s.emplace(p);
    }
    while ((int) s.size() > k) {
      sum -= (--s.end())->first;
      s.erase(--s.end());
    }
    if ((int) s.size() == k && sum <= T) {
      for (auto &p : s) {
        res.push_back(p.second);
      }
      break;
    }
  }
  int sz = (int) res.size();
  printf("%d\n%d\n", sz, sz);
  for (int i = 0; i < sz; i++) {
    if (i > 0) {
      putchar(' ');
    }
    printf("%d", res[i] + 1);
  }
  printf("\n");
  return 0;
}

#include <iostream>
#include <set>
#include <vector>
#include <string>

using namespace std;

bool ls(const string& a, const string& b) {
	if (a.length() == b.length()) return a < b;
	return a.length() < b.length();
}

struct Expression {
	int p, t;
	string e;

	Expression(string _e, int t_, int _p) : e(_e), t(t_), p(_p) {}

	bool operator < (const Expression& ex) const {
		if (ex.e == e) {
			if (t != ex.t) {
				return t < ex.t;
			}
			return p < ex.p;
		}
		return ls(e, ex.e);
	}
};

set<Expression> q;

const int FULL = 0xff;
const vector<int> B = {1, 2, 4, 8, 16, 32, 64, 128};
const int X_TABLE = B[4] + B[5] + B[6] + B[7];
const int Y_TABLE = B[2] + B[3] + B[6] + B[7];
const int Z_TABLE = B[1] + B[3] + B[5] + B[7];

string dp[1 << 8][3];

void add(int pr, const string& s, int mask) {
	if (dp[mask][pr].empty() || ls(s, dp[mask][pr])) {
		dp[mask][pr] = s;
		Expression e(s, mask, pr);
		q.insert(e);
	}
}

int main() {
	add(2, "x", X_TABLE);
	add(2, "y", Y_TABLE);
	add(2, "z", Z_TABLE);
	while (!q.empty()) {
		auto e = *q.begin();
		q.erase(q.begin());

		if (e.p == 2) {
			add(2, "!" + e.e, ~e.t & FULL);
			add(1, e.e, e.t);
		}

		if (e.p == 1) {
			for (int mask = 0; mask < FULL; ++mask) {
				if (!dp[mask][2].empty()) {
					add(1, dp[mask][2] + "&" + e.e, mask & e.t);
					add(1, e.e + "&" + dp[mask][2], mask & e.t);
				}
			}
			add(2, "(" + e.e + ")", e.t);
			add(0, e.e, e.t);
		}

		if (e.p == 0) {
			for (int mask = 0; mask < FULL; ++mask) {
				for (int pr = 1; pr <= 2; ++pr) {
					if (!dp[mask][pr].empty()) {
						add(0, dp[mask][pr] + "|" + e.e, mask | e.t);
						add(0, e.e + "|" + dp[mask][pr], mask | e.t);
					}
				}
			}
			add(2, "(" + e.e + ")", e.t);
		}
	}

	
	int n;
	cin >> n;
	while (n--) {
		string s;
		cin >> s;
		int mask = 0;
		for (int i = 0; i < 8; ++i) {
			if (s[i] == '1') {
				mask |= (1 << i);
			}
		}

		cout << dp[mask][0] << endl;
	}

	return 0;
}

#include <bits/stdc++.h>

using namespace std;

string res[256][3];
bool changed;

void update(string &a, string &b) {
  if (a == "" || (b.length() < a.length() || (b.length() == a.length() && b < a))) {
    changed = true;
    a = b;
  }
}

int main() {
  res[(1 << 4) + (1 << 5) + (1 << 6) + (1 << 7)][0] = "x";
  res[(1 << 2) + (1 << 3) + (1 << 6) + (1 << 7)][0] = "y";
  res[(1 << 1) + (1 << 3) + (1 << 5) + (1 << 7)][0] = "z";
  changed = true;
  while (changed) {
    changed = false;
    for (int i = 0; i < 256; i++) {
      for (int j = 0; j < 3; j++) {
        if (res[i][j] == "") {
          continue;
        }
        { // op == 0
          string s = res[i][j];
          if (j > 0) {
            s = "(" + s + ")";
          }
          s = "!" + s;
          update(res[i ^ 255][0], s);
        }
        for (int ii = 0; ii < 256; ii++) {
          for (int jj = 0; jj < 3; jj++) {
            if (res[ii][jj] == "") {
              continue;
            }
            for (int op = 1; op <= 2; op++) {
              string s = res[i][j];
              if (j > op) {
                s = "(" + s + ")";
              }
              string t = res[ii][jj];
              if (jj > op) {
                t = "(" + t + ")";
              }
              string w = s + (op == 1 ? '&' : '|') + t;
              update(res[op == 1 ? (i & ii) : (i | ii)][op], w);
            }
          }
        }
      }
    }
  }
  int tt;
  cin >> tt;
  while (tt--) {
    string z;
    cin >> z;
    int mask = 0;
    for (int i = 0; i < 8; i++) {
      mask |= (z[i] - '0') << i;
    }
    string best = "";
    for (int j = 0; j < 3; j++) {
      update(best, res[mask][j]);
    }
    cout << best << endl;
  }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int md = 998244353;

inline void add(int &a, int b) {
  a += b;
  if (a >= md) a -= md;
}

inline void sub(int &a, int b) {
  a -= b;
  if (a < 0) a += md;
}

inline int mul(int a, int b) {
  return (int) ((long long) a * b % md);
}

inline int power(int a, long long b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) {
      res = mul(res, a);
    }
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}

inline int inv(int a) {
  return power(a, md - 2);
}

int main() {
  int n, P, Q;
  cin >> n >> P >> Q;
  int p = mul(P, inv(Q));
  vector< vector<int> > p_win(n + 1, vector<int>(n + 1, 0));
  p_win[0][0] = 1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= i; j++) {
      add(p_win[i + 1][j], mul(p_win[i][j], power(p, j)));
      add(p_win[i + 1][j + 1], mul(p_win[i][j], power((1 - p + md) % md, i - j)));
    }
  }
  vector<int> p_strong(n + 1);
  for (int i = 1; i <= n; i++) {
    p_strong[i] = 1;
    for (int j = 1; j < i; j++) {
      sub(p_strong[i], mul(p_strong[j], p_win[i][j]));
    }
  }
  vector<int> res(n + 1);
  res[1] = 0;
  for (int i = 2; i <= n; i++) {
    res[i] = 0;
    for (int j = 1; j < i; j++) {
      int coeff = mul(p_strong[j], p_win[i][j]);
      int games = (res[j] + res[i - j]) % md;
      add(games, j * (j - 1) / 2 + j * (i - j));
      add(res[i], mul(coeff, games));
    }
    add(res[i], mul(i * (i - 1) / 2, p_strong[i]));
    res[i] = mul(res[i], inv((1 - p_strong[i] + md) % md));
  }
  cout << res[n] << endl;
  return 0;
}

def dlog(x, n):
  bigMod = 5 ** n
  ans = [None, 0, 1, 3, 2][x % 5]
  val = 2 ** ans % bigMod
  mod, phi = 5, 4
  phiVal = 2 ** phi % bigMod
  for i in range(2, n + 1):
    nextMod = mod * 5
    while val % nextMod != x % nextMod:
      val = val * phiVal % bigMod
      ans += phi
    phi *= 5
    phiVal = (phiVal *
              phiVal % bigMod *
              phiVal % bigMod *
              phiVal % bigMod *
              phiVal % bigMod)
    mod = nextMod
  return ans

def main():
  inp = input()
  n = len(inp)
  a = int(inp)
  for m in range(n + 1):
    l = a * 10 ** m
    x, mod = l, 2 ** (n + m)
    if x % mod != 0:
      x += mod - x % mod
    if x % 5 == 0:
      x += mod
    if x < l + 10 ** m:
      assert x % mod == 0 and x % 5 != 0
      x = x // mod
      mod = 5 ** (n + m)
      print(n + m + dlog(x % mod, n + m))
      return
  assert False

if __name__ == '__main__':
  cnt = int(input())
  for i in range(cnt):
    main()

#include <bits/stdc++.h>

using namespace std;

inline long long mul(long long a, long long b, long long md) {
  long long res = 0;
  while (b > 0) {
    if (b & 1) {
      res += a; if (res >= md) res -= md;
    }
    a += a; if (a >= md) a -= md;
    b >>= 1;
  }
  return res;
}

inline long long power(long long a, long long b, long long md) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) {
      res = mul(res, a, md);
    }
    a = mul(a, a, md);
    b >>= 1;
  }
  return res;
}

int main() {
  int tt;
  cin >> tt;
  while (tt--) {
    long long a;
    cin >> a;
    int n = (int) to_string(a).length();
    for (int m = 0; ; m++) {
      long long b = (-a) & ((1LL << (n + m)) - 1);
      if ((a + b) % 5 == 0) {
        b += (1LL << (n + m));
      }
      if ((b == 0 && m == 0) || (int) to_string(b).length() <= m) {
        long long c = (a + b) >> (n + m);
        long long t = vector<long long>{-1, 0, 1, 3, 2}[c % 5];
        long long p5 = 5;
        for (int i = 1; i < n + m; i++) {
          while (power(2, t, p5 * 5) != c % (p5 * 5)) {
            t += p5 / 5 * 4;
          }
          p5 *= 5;
        }
        t += n + m;
        cout << t << endl;
        break;
      }
      a *= 10;
    }
  }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int md = 998244353;

inline void add(int &a, int b) {
  a += b;
  if (a >= md) a -= md;
}

inline void sub(int &a, int b) {
  a -= b;
  if (a < 0) a += md;
}

inline int mul(int a, int b) {
  return (int) ((long long) a * b % md);
}

inline int power(int a, long long b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) {
      res = mul(res, a);
    }
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}

inline int inv(int a) {
  return power(a, md - 2);
}

const int N = 77;

int C[N][N];

typedef vector<int> poly;

poly integrate(poly a) {
  poly b = {0};
  for (int i = 0; i < (int) a.size(); i++) {
    b.push_back(mul(a[i], inv(i + 1)));
  }
  return b;
}

void sub(poly &a, poly b) {
  while (a.size() < b.size()) {
    a.push_back(0);
  }
  for (int i = 0; i < (int) b.size(); i++) {
    sub(a[i], b[i]);
  }
}

poly plug(poly a, int delta) {
  // a(x + delta)
  poly b(a.size(), 0);
  for (int i = 0; i < (int) a.size(); i++) {
    for (int j = 0; j <= i; j++) {
      add(b[j], mul(a[i], mul(C[i][j], power(delta, i - j))));
    }
  }
  return b;
}

int eval(poly a, int x) {
  int res = 0;
  for (int i = (int) a.size() - 1; i >= 0; i--) {
    res = mul(res, x);
    add(res, a[i]);
  }
  return res;
}

const int COEFF = 1000000;

int main() {
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      C[i][j] = (j == 0 ? 1 : (i == 0 ? 0 : (C[i - 1][j] + C[i - 1][j - 1]) % md));
    }
  }
  int n;
  cin >> n;
  vector<int> x(n), fracs;
  for (int i = 0; i < n; i++) {
    double foo;
    cin >> foo;
    x[i] = (int) (foo * COEFF + 0.5);
    fracs.push_back(x[i] % COEFF);
  }
  fracs.push_back(0);
  sort(fracs.begin(), fracs.end());
  fracs.resize(unique(fracs.begin(), fracs.end()) - fracs.begin());
  int cnt = (int) fracs.size();
  vector<int> point(n * cnt + 1);
  for (int i = 0; i <= n * cnt; i++) {
    point[i] = mul(i / cnt * COEFF + fracs[i % cnt], inv(COEFF));
  }
  vector<int> cut(n);
  for (int i = 0; i < n; i++) {
    cut[i] = (int) (find(point.begin(), point.end(), mul(x[i], inv(COEFF))) - point.begin());
  }
  vector<poly> a(n * cnt);
  for (int i = 0; i < n * cnt; i++) {
    a[i] = {i < min(cnt, cut[0]) ? 1 : 0};
  }
  for (int id = 1; id < n; id++) {
    for (int i = 0; i < n * cnt; i++) {
      a[i] = integrate(a[i]);
    }
    for (int i = n * cnt - 1; i >= 0; i--) {
      sub(a[i][0], eval(a[i], point[i]));
      for (int j = i - 1; j >= i - cnt && j >= 0; j--) {
        add(a[i][0], eval(a[j], point[j + 1]));
        if (j > i - cnt) {
          sub(a[i][0], eval(a[j], point[j]));
        } else {
          sub(a[i], plug(a[i - cnt], md - 1));
        }
      }
    }
    for (int i = cut[id]; i < n * cnt; i++) {
      a[i] = {0};
    }
  }
  int ans = 0;
  for (int i = 0; i < n * cnt; i++) {
    poly b = integrate(a[i]);
    add(ans, eval(b, point[i + 1]));
    sub(ans, eval(b, point[i]));
  }
  printf("%d\n", ans);
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int md = 998244353;

inline void add(int &a, int b) {
  a += b;
  if (a >= md) a -= md;
}

inline void sub(int &a, int b) {
  a -= b;
  if (a < 0) a += md;
}

inline int mul(int a, int b) {
  return (int) ((long long) a * b % md);
}

inline int power(int a, long long b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) {
      res = mul(res, a);
    }
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}

inline int inv(int a) {
  return power(a, md - 2);
}

typedef vector<int> poly;

poly integrate(poly a) {
  poly b = {0};
  for (int i = 0; i < (int) a.size(); i++) {
    b.push_back(mul(a[i], inv(i + 1)));
  }
  return b;
}

void sub(poly &a, poly b) {
  while (a.size() < b.size()) {
    a.push_back(0);
  }
  for (int i = 0; i < (int) b.size(); i++) {
    sub(a[i], b[i]);
  }
}

int eval(poly a, int x) {
  int res = 0;
  for (int i = (int) a.size() - 1; i >= 0; i--) {
    res = mul(res, x);
    add(res, a[i]);
  }
  return res;
}

const int COEFF = 1000000;

int main() {
  int n;
  cin >> n;
  vector<int> x(n), fracs;
  for (int i = 0; i < n; i++) {
    double foo;
    cin >> foo;
    x[i] = (int) (foo * COEFF + 0.5);
    fracs.push_back(x[i] % COEFF);
  }
  fracs.push_back(0);
  sort(fracs.begin(), fracs.end());
  fracs.resize(unique(fracs.begin(), fracs.end()) - fracs.begin());
  int cnt = (int) fracs.size();
  vector<int> point(n * cnt + 1);
  for (int i = 0; i <= n * cnt; i++) {
    point[i] = i / cnt * COEFF + fracs[i % cnt];
  }
  vector<int> cut(n);
  for (int i = 0; i < n; i++) {
    cut[i] = (int) (find(point.begin(), point.end(), x[i]) - point.begin());
  }
  vector<int> sz(n * cnt);
  for (int i = 0; i < n * cnt; i++) {
    sz[i] = mul((point[i + 1] - point[i] + md) % md, inv(COEFF));
  }
  vector<poly> a(n * cnt);
  vector<int> sum(n * cnt);
  for (int i = 0; i < n * cnt; i++) {
    a[i] = i < min(cnt, cut[0]) ? vector<int>{0, 1} : vector<int>{0};
    sum[i] = a[i].size() == 1 ? 0 : sz[i];
  }
  for (int id = 1; id < n; id++) {
    for (int i = n * cnt - 1; i >= 0; i--) {
      if (i >= cut[id]) {
        a[i] = {0};
        sum[i] = 0;
      } else {
        for (int j = i - 1; j >= i - cnt && j >= 0; j--) {
          add(a[i][0], sum[j]);
        }
        if (i - cnt >= 0) {
          sub(a[i], a[i - cnt]);
        }
        a[i] = integrate(a[i]);
        sum[i] = eval(a[i], sz[i]);
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < n * cnt; i++) {
    add(ans, sum[i]);
  }
  printf("%d\n", ans);
  return 0;
}

n = int(input())
results = []
for i in range(n):
    results.append(list(map(int, input().split())))

for r in results:
    if r[0] != r[1]:
        print("rated")
        exit()

for i in range(n):
    for j in range(i):
        if results[i][0] > results[j][0]:
            print("unrated")
            exit()

print("maybe")

#include <bits/stdc++.h>

using namespace std;

int main() {
  int p, x, y;
  cin >> p >> x >> y;
  for (int s = y; ; s++) {
    if (s % 50 != x % 50) {
      continue;
    }
    bool me = false;
    int i = s / 50 % 475;
    for (int j = 0; j < 25; j++) {
      i = (i * 96 + 42) % 475;
      if (i + 26 == p) {
        me = true;
        break;
      }
    }
    if (me) {
      printf("%d\n", (max(0, s - x) + 50) / 100);
      break;
    }
  }
  return 0;
}

p, x, y = map(int, input().split())

def check(s):
    i = (s // 50) % 475
    for t in range(25):
        i = (i * 96 + 42) % 475
        if 26 + i == p:
            return True
    return False

for up in range(500):
    for down in range(500):
        if x + 100 * up - 50 * down >= y and check(x + 100 * up - 50 * down):
            print(up)
            exit()

assert(False)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

bool check(ll x, ll y, ll p, ll q, ll t) {
  return p * t >= x && q * t - p * t >= y - x;
}

void solve() {
  ll x, y, p, q;
  scanf("%lld%lld%lld%lld", &x, &y, &p, &q);

  ll l = -1;
  ll r = (ll) 1e9;

  if (!check(x, y, p, q, r)) {
    printf("-1\n");
    return;
  }

  while (r - l > 1) {
    ll m = (l + r) / 2;
    if (check(x, y, p, q, m)) {
      r = m;
    } else {
      l = m;
    }
  }

  printf("%lld\n", r * q - y);
}

int main() {
  int t;
  scanf("%d", &t);

  while (t--) {
    solve();
  }

  return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int tt;
  cin >> tt;
  while (tt--) {
    int x, y, p, q;
    cin >> x >> y >> p >> q;
    if (p == 0) {
      cout << (x == 0 ? 0 : -1) << endl;
      continue;
    }
    if (p == q) {
      cout << (x == y ? 0 : -1) << endl;
      continue;
    }
    int t1 = (x + p - 1) / p;
    int t2 = ((y - x) + (q - p) - 1) / (q - p);
    cout << (q * 1LL * max(t1, t2) - y) << endl;
  }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 123456;
const int m = 5;
const int k = 6;

int a[N][m];
int score[N];
int cost[m];
int solved[m];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      scanf("%d", a[i] + j);
      if (a[i][j] != -1) {
        solved[j]++;
      }
    }
  }
  for (int bots = 0; bots <= ((1 << (k - 1)) - 1) * n; bots++) {
    for (int j = 0; j < m; j++) {
      int total = n + bots;
      int cur = solved[j];
      if (a[0][j] != -1 && a[1][j] != -1 && a[0][j] > a[1][j]) {
        cur += bots;
      }
      cost[j] = 500;
      while (cost[j] < 500 * k && 2 * cur <= total) {
        cur *= 2;
        cost[j] += 500;
      }
    }
    for (int i = 0; i < 2; i++) {
      score[i] = 0;
      for (int j = 0; j < m; j++) {
        if (a[i][j] != -1) {
          score[i] += cost[j] / 250 * (250 - a[i][j]);
        }
      }
    }
    if (score[0] > score[1]) {
      printf("%d\n", bots);
      return 0;
    }
  }
  printf("%d\n", -1);
  return 0;
}

n = int(input())
a = sorted(list(map(int, input().split())))

maxe = max(a)
cnt = []
cur = 1
k = 0
i = 0
while i < n:
    cnt.append(0)
    while i < n and a[i] < cur:
        cnt[2 * k] += 1
        i += 1
    cnt.append(0)
    while i < n and a[i] == cur:
        cnt[2 * k + 1] += 1
        i += 1
    k += 1
    cur *= 2
cnt.append(0)
cnt.append(0)
maxe = len(cnt) - 1

maxk = cnt[1]
was = False
for l in range(maxk):
    cur = 1
    while cnt[cur] > 0:
        cnt[cur] -= 1
        cur += 2
    cnt[cur] -= 1
    cursum = 0
    ok = True
    for t in range(maxe, 0, -1):
        cursum += cnt[t]
        if cursum > 0:
            ok = False
            break
    if ok:
        print(l + 1, end=" ")
        was = True

if not was:
    print(-1)

#include <bits/stdc++.h>

using namespace std;

const int MAX = 66;

int power[MAX + 10];
int between[MAX + 10];
int extra[MAX + 10];
int ende[MAX + 10];

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    long long foo;
    cin >> foo;
    int cc = 0;
    bool good = true;
    while (foo > 1) {
      if (foo & 1) {
        good = false;
      }
      cc++;
      foo >>= 1;
    }
    if (good) {
      power[cc]++;
    } else {
      between[cc]++;
    }
  }
  int low = 1, high = power[0] + 1;
  while (low < high) {
    int mid = (low + high) >> 1;
    int cur = mid;
    for (int i = 0; i < MAX; i++) {
      extra[i] = power[i] - cur;
      int new_cur = min(cur, power[i + 1]);
      ende[i] = cur - new_cur;
      cur = new_cur;
    }
    bool fail = false;
    int open = 0;
    for (int i = MAX - 1; i >= 0; i--) {
      open += ende[i];
      open -= between[i];
      open -= extra[i + 1];
      if (open < 0) {
        fail = true;
        break;
      }
    }
    open -= extra[0];
    if (open < 0) {
      fail = true;
    }
    if (fail) {
      low = mid + 1;
    } else {
      high = mid;
    }
  }
  if (low > power[0]) {
    cout << -1 << endl;
    return 0;
  }
  for (int i = low; i <= power[0]; i++) {
    cout << i << " ";
  }
  cout << endl;
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

const long long inf = (long long) 1e18;

const int N = 2010;

int a[N][N];
long long d[N];
bool used[N];

int main() {
  // reading input data
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    a[i][i] = 0;
    for (int j = i + 1; j < n; j++) {
      scanf("%d", a[i] + j);
      a[j][i] = a[i][j];
    }
  }
  // finding minimum edge weight
  int min_edge = a[0][1];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i != j) {
        min_edge = min(min_edge, a[i][j]);
      }
    }
  }
  // subtracting minimum edge weight from all edge weights
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i != j) {
        a[i][j] -= min_edge;
      }
    }
  }
  // initializing distance array
  for (int i = 0; i < n; i++) {
    d[i] = inf;
    for (int j = 0; j < n; j++) {
      if (i != j) {
        d[i] = min(d[i], 2LL * a[i][j]);
      }
    }
    used[i] = false;
  }
  // running Dijkstra
  for (int it = 0; it < n; it++) {
    long long min_d = inf;
    int ver = -1;
    for (int i = 0; i < n; i++) {
      if (!used[i] && d[i] < min_d) {
        min_d = d[i];
        ver = i;
      }
    }
    used[ver] = true;
    for (int i = 0; i < n; i++) {
      d[i] = min(d[i], d[ver] + a[ver][i]);
    }
  }
  // printing result
  for (int i = 0; i < n; i++) {
    cout << (d[i] + (long long) min_edge * (n - 1)) << endl;
  }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

inline int signum(int x) {
  return (x < 0 ? -1 : (x > 0 ? 1 : 0));
}

const int inf = (int) 1e9;

const int N = 500010;

pair <int, int> a[N];
int pos[N];

pair <int, int> mn[4 * N];
int add[4 * N];

void push(int x) {
  add[x + x] += add[x];
  mn[x + x].first += add[x];
  add[x + x + 1] += add[x];
  mn[x + x + 1].first += add[x];
  add[x] = 0;
}

void pull(int x) {
  mn[x] = min(mn[x + x], mn[x + x + 1]);
}

void build(int x, int l, int r) {
  add[x] = 0;
  if (l == r) {
    mn[x] = make_pair(a[l].first, l);
    return;
  }
  int y = (l + r) >> 1;
  build(x + x, l, y);
  build(x + x + 1, y + 1, r);
  pull(x);
}

void modify(int x, int l, int r, int ll, int rr, int v) {
  if (ll <= l && r <= rr) {
    add[x] -= v;
    mn[x].first -= v;
    return;
  }
  push(x);
  int y = (l + r) >> 1;
  if (ll <= y) {
    modify(x + x, l, y, ll, rr, v);
  }
  if (rr > y) {
    modify(x + x + 1, y + 1, r, ll, rr, v);
  }
  pull(x);
}

pair <int, int> find_min(int x, int l, int r, int ll, int rr) {
  if (ll <= l && r <= rr) {
    return mn[x];
  }
  push(x);
  int y = (l + r) >> 1;
  pair <int, int> res = make_pair(inf, -1);
  if (ll <= y) {
    res = min(res, find_min(x + x, l, y, ll, rr));
  }
  if (rr > y) {
    res = min(res, find_min(x + x + 1, y + 1, r, ll, rr));
  }
  pull(x);
  return res;
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i].first);
    a[i].second = i;
  }
  sort(a, a + n);
  for (int i = 0; i < n; i++) {
    pos[a[i].second] = i;
  }
  build(1, 0, n - 1);
  set <int> minus, zero, plus;
  for (int id = 0; id < n; id++) {
    int i = pos[id];
    auto p = find_min(1, 0, n - 1, i, i);
    int vote = signum(p.first);
    if (vote == 0) {
      zero.insert(i);
    } else {
      if (vote == -1) {
        minus.insert(i);
        modify(1, 0, n - 1, i, n - 1, -1);
        int last_minus = *(--minus.end());
        if (a[last_minus].first == 1 - (int) minus.size()) {
          minus.erase(last_minus);
          modify(1, 0, n - 1, last_minus, n - 1, 1);
          zero.insert(last_minus);
        } else {
          if (!zero.empty()) {
            int first_zero = *(zero.begin());
            zero.erase(first_zero);
            plus.insert(first_zero);
            modify(1, 0, n - 1, first_zero, n - 1, 1);
          }
        }
      } else {
        plus.insert(i);
        modify(1, 0, n - 1, i, n - 1, 1);
        auto q = find_min(1, 0, n - 1, i, n - 1);
        if (q.first == -1) {
          int pos = q.second;
          plus.erase(pos);
          modify(1, 0, n - 1, pos, n - 1, -1);
          zero.insert(pos);
        }
      }
    }
    printf("%d\n", (int) plus.size() - (int) minus.size());
  }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;
template<typename T>
using pair2 = pair<T, T>;

#ifdef WIN32
    #define LLD "%I64d"
#else
    #define LLD "%lld"
#endif

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

const long double pi = acos((ld)-1.0);

const int maxn = 1 << 16;

typedef complex<double> comp;

comp oddc[maxn], evenc[maxn], tmp[maxn];
comp w[maxn], invw[maxn];
ll odd[maxn], even[maxn];
int oldodd[maxn], oldeven[maxn];
int btr[maxn];
int n, A, mod;
int st2;
int answer;

inline int bitrev(int x)
{
    return btr[x];
}

void fft(comp *a, int n, comp *w, comp *res)
{
    for (int i = 0; i < n; i++) res[bitrev(i)] = a[i];
    for (int len = 2; len <= n; len *= 2)
    {
        int step = n / len;
        for (int i = 0; i < n; i += len)
        {
            int curw = 0;
            for (int j = 0; j < len / 2; j++)
            {
                comp x = res[i + j];
                comp y = res[i + len / 2 + j] * w[curw];
                res[i + j] = x + y;
                res[i + len / 2 + j] = x - y;
                curw += step;
            }
        }
    }
}

void preparefft(int n)
{
    for (int i = 0; i < n; i++)
    {
        int cur = i;
        for (int j = 0; (1 << j) < n; j++)
        {
            btr[i] = (btr[i] << 1) | (cur & 1);
            cur >>= 1;
        }
    }
    for (int i = 0; i < n; i++)
    {
        w[i] = comp(cos(2 * pi / n * i), sin(2 * pi / n * i));
        invw[i] = w[i];
    }
    reverse(invw + 1, invw + n);
}

void conv(ll *from, comp *to)
{
    for (int i = n + 1; i < st2; i++) tmp[i] = 0;
    for (int i = 0; i <= n; i++) tmp[i] = from[i];
    fft(tmp, st2, w, to);
}

void convback(comp *from, ll *to)
{
    fft(from, st2, invw, tmp);
    for (int i = 0; i < st2; i++) tmp[i] /= st2;
    for (int i = 0; i <= n; i++)
    {
        to[i] = (ll)(tmp[i].real() + 0.5);
        assert(abs(tmp[i].imag()) < 0.1);
    }
}

void addans()
{
    for (int i = 1; i <= n; i += 2) answer = (answer + odd[i]) % mod;
}

void go(int A)
{
    if (A == 1)
    {
        even[0] = 1;
        odd[0] = 0;
        odd[1] = 1;
        addans();
        return;
    }
    go(A / 2);

    for (int i = 0; i <= n; i++) oldodd[i] = odd[i];
    for (int i = 0; i <= n; i++) oldeven[i] = even[i];
    conv(even, evenc);
    conv(odd, oddc);
    for (int i = 0; i < st2; i++)
    {
        if ((A / 2) % 2 == 0)
        {
            tie(oddc[i], evenc[i])  = make_pair((oddc[i] + evenc[i]) * oddc[i], (oddc[i] + evenc[i]) * (evenc[i] - (comp)1));
        } else
        {
            tie(evenc[i], oddc[i])  = make_pair((oddc[i] + evenc[i]) * oddc[i], (oddc[i] + evenc[i]) * (evenc[i] - (comp)1));
        }
    }
    convback(oddc, odd);
    convback(evenc, even);
    for (int i = n + 1; i <= 2 * n; i++)
    {
        odd[i] = 0;
        even[i] = 0;
    }
    for (int i = 0; i <= n; i++)
    {
        odd[i] = (odd[i] + oldodd[i]) % mod;
        even[i] = (even[i] + oldeven[i]) % mod;
    }
    if (A % 2 == 1)
    {
        for (int i = n; i >= 1; i--)
        {
            odd[i] = (odd[i] + odd[i - 1] + even[i - 1]) % mod;
        }
    }
    addans();
}

int main()
{
    cin >> n >> A >> mod;
    if (A == 1)
    {
        cout << 0 << endl;
        return 0;
    }
    st2 = 0;
    while ((1 << st2) <= n) st2++;
    st2++;
    st2 = 1 << st2;
    preparefft(st2);
    go(A / 2);
    cout << answer << endl;
    return 0;
}