For this Question: Natasha and Scott are playing a game with a single pile of stones. Initially the pile contains K stones. The players alternate turns, with Natasha starting first. In one move, the player can either add any odd number of stones to the pile or remove any odd number of stones from the pile. The rules are as follows:

1. The number of stones should not go below 0 or go above N.
2. If at any instance of the game there were x stones, the number of stones cannot be x thereafter.
3. Initially some set of numbers S = {s<sub>1</sub>, s<sub>2</sub>, s<sub>3</sub>, … } are given which are blocked, which means that we are not allowed to play a move after which we will end up with a number of stones which belongs to this set.
4. The player who cannot move loses.

For a given set S, let F(S) denote the number of K’s (0 ≤ K ≤ N) such that Natasha has a winning strategy for that game. They need you to find <b>&#x2211; F(S)</b> where summation is over all the subsets of {0, 1, 2, ... N}.

This number can be very large, so they want you to print it modulo 998244353.The file contains multiple test cases. The first line contains an integer T - the number of test cases. 
Then T lines follows, each line containing an integer N. 

<b>Constraints:</b>
1 ≤ T ≤ 10<sup>6</sup>
1 ≤ N ≤ 10<sup>6</sup>
It is guaranteed that the sum of N over all tests is less than or equal to 10<sup>6</sup>.Output T lines.
The i<sup>th</sup> line should contain a single integer, the answer to the i<sup>th</sup> test case.Sample Input
3
1
2
3

Sample Output
2
5
16

Explanation: 
Test Case 1: N = 1. There are 4 subsets {}, {0}, {1}, {0,1}.

a) {0,1}: The non Blocked are {}: No winning positions, as Natasha cannot even choose the first position.
b) {1}. The non Blocked are {0}: Clearly Natasha must start with 0 as only one position, but she cannot make move so she loses.
c) {0}. The non Blocked are {1}: Similar to (a).
d) {}.  The non Blocked are {0,1}: In this case if Natasha start with 0, she can make first move to 1, then Scott does not have any valid move, so Natasha wins. similarly if she starts with 1.

So total winning positions = 0 + 0 + 0 + 2 = 2., I have written this Solution Code: #include <bits/stdc++.h>


using namespace std;

#define int long long

const int mod = 998'244'353;

const long long INF = 2e18 + 10;


#ifdef int
      #undef int
#endif


template <typename T>
T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a; swap(a, m);
    u -= t * v; swap(u, v);
  }
  assert(m == 1);
  return u;
}
 
template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;
 
  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }
 
  template <typename U>
  static Type normalize(const U& x) {
    Type v;
    if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
    else v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }
 
  const Type& operator()() const { return value; }
  template <typename U>
  explicit operator U() const { return static_cast<U>(value); }
  constexpr static Type mod() { return T::value; }
 
  Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
  Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
  template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
  template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
  Modular& operator++() { return *this += 1; }
  Modular& operator--() { return *this -= 1; }
  Modular operator++(signed) { Modular result(*this); *this += 1; return result; }
  Modular operator--(signed) { Modular result(*this); *this -= 1; return result; }
  Modular operator-() const { return Modular(-value); }
 
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
#ifdef _WIN32
    uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
    uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;
    asm(
      "divl %4; \n\t"
      : "=a" (d), "=d" (m)
      : "d" (xh), "a" (xl), "r" (mod())
    );
    value = m;
#else
    value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
#endif
    return *this;
  }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value, Modular>::type& operator*=(const Modular& rhs) {
    int64_t q = static_cast<int64_t>(static_cast<long double>(value) * rhs.value / mod());
    value = normalize(value * rhs.value - q * mod());
    return *this;
  }
  template <typename U = T>
  typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) {
    value = normalize(value * rhs.value);
    return *this;
  }
 
  Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }
 
  template <typename U>
  friend const Modular<U>& abs(const Modular<U>& v) { return v; }
 
  template <typename U>
  friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);
 
  template <typename U>
  friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);
 
  template <typename U>
  friend std::istream& operator>>(std::istream& stream, Modular<U>& number);
 
 private:
  Type value;
};
 
template <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
template <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }
template <typename T, typename U> bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; }
 
template <typename T> bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
 
template <typename T> bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; }
 
template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
 
template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
 
template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
 
template <typename T> Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
 
template<typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
  assert(b >= 0);
  Modular<T> x = a, res = 1;
  U p = b;
  while (p > 0) {
    if (p & 1) res *= x;
    x *= x;
    p >>= 1;
  }
  return res;
}
 
template <typename T>
bool IsZero(const Modular<T>& number) {
  return number() == 0;
}
 
template <typename T>
string to_string(const Modular<T>& number) {
  return to_string(number());
}
 
template <typename T>
std::ostream& operator<<(std::ostream& stream, const Modular<T>& number) {
  return stream << number();
}
 
template <typename T>
std::istream& operator>>(std::istream& stream, Modular<T>& number) {
  typename common_type<typename Modular<T>::Type, int64_t>::type x;
  stream >> x;
  number.value = Modular<T>::normalize(x);
  return stream;
}
 
/*
using ModType = int;
 
struct VarMod { static ModType value; };
ModType VarMod::value;
ModType& md = VarMod::value;
using Mint = Modular<VarMod>;
 
*/
 
constexpr int md = mod;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
 
Mint pwr(Mint a, int k) {
    Mint ans = 1;
    while(k) {
        if(k & 1) ans = ans * a;
        a = a * a;
        k >>= 1;
    }
    return ans;
}

#define int long long 


const int MAXN=1e6+10;
vector<Mint> fac(MAXN);
vector<Mint> infac(MAXN);
void build_factorial()
{
    fac[0]=1;
    infac[0]=1;
    for(int i=1;i<MAXN;i++)
    {
        fac[i]=(fac[i-1]*i);
    }
    infac[MAXN-1] = pwr(fac[MAXN -1], mod - 2);

    for(int i= MAXN-2;i>=0;i--)
    {
        infac[i] = infac[i+1] *(i + 1);
    }
}
Mint ncr(int n, int r)
{
    if(n == 0)
        return 0 ;
    if(n<r)
        return 0;
    return 1LL*fac[n] * infac[r]  * infac[n-r];
}



Mint solv(int n)
{





    Mint ans = 0;


    int even = (n + 1) /2;
    int odd = (n + 1) - even;

    vector<Mint> pref_sm_odd( odd + 1);
    vector<Mint> pref_sm_even( even + 1);

    pref_sm_even[0] = 1;
    pref_sm_odd[0] = 1;
    for(int i = 1;i<=odd;i++)
    {
        pref_sm_odd[i] = pref_sm_odd[i-1] + ncr(odd, i);
    }

    for(int i = 1;i<=even;i++)
    {
        pref_sm_even[i] = pref_sm_even[i-1] + ncr(even, i);
    }



    for(int left_side_win = 1;left_side_win <=even;left_side_win ++ )
    {
        Mint pref = pref_sm_odd[odd] - pref_sm_odd[left_side_win-1];
        ans += left_side_win * ( ncr( even, left_side_win ) * pref);
    }



    for(int right_side_win = 1;right_side_win <=odd;right_side_win ++ )
    {
        Mint pref = pref_sm_even[even] - pref_sm_even[right_side_win-1];
        ans += right_side_win * ( ncr( odd, right_side_win ) * pref);
    }


    return ans;

}





void stress()
{

    for(int n = 1;n<=10;n++)
    {
        cout<<n<<" "<<solv(n)<<endl;
    }    


    exit(0);

}
void solve()
{
    build_factorial( );

    // stress();

    int t = 1;
    cin>>t;



    for(int T  =1;T<=t;T++)
    {

        int n;
        cin>>n;
        assert(n);
        cout<<solv(n)<<'\n';
    }



}




signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cerr.tie(NULL);

#ifndef ONLINE_JUDGE
    if (fopen("INPUT.txt", "r"))
    {
        freopen("INPUT.txt", "r", stdin);
        freopen("OUTPUT.txt", "w", stdout);

    }
#else
    #ifdef ASC
    namespace fs = std::filesystem;
    std::string path = "./";
    string filename;
    for (const auto & entry : fs::directory_iterator(path)){
        if( entry.path().extension().string() == ".in"){
            filename = entry.path().filename().stem().string();
        }
    }
    if(filename != ""){
        string input_file = filename +".in";
        string output_file = filename +".out";
        if (fopen(input_file.c_str(), "r"))
        {
            freopen(input_file.c_str(), "r", stdin);
            freopen(output_file.c_str(), "w", stdout);
        }
    }
    #endif
#endif
    // auto clk = clock();
    // -------------------------------------Code starts here---------------------------------------------------------------------

    signed t = 1;
    // cin >> t;

    for (signed test = 1; test <= t; test++)
    {
        // cout<<"Case #"<<test<<": ";
        // cout<<endl;

        solve();
    }

    // -------------------------------------Code ends here------------------------------------------------------------------

    // clk = clock() - clk;

    #ifndef ONLINE_JUDGE
    // cerr << fixed << setprecision(6) << "\nTime: " << ((float)clk) / CLOCKS_PER_SEC << "\n";
    #endif
    return 0;
}
, In this Programming Language: C++, Now tell me if this Code is compilable or not?