結果
| 問題 |
No.2067 ±2^k operations
|
| ユーザー |
 ecottea
|
| 提出日時 | 2025-07-16 03:24:46 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 33,029 bytes |
| コンパイル時間 | 5,388 ms |
| コンパイル使用メモリ | 273,536 KB |
| 実行使用メモリ | 7,716 KB |
| 最終ジャッジ日時 | 2025-07-16 03:24:57 |
| 合計ジャッジ時間 | 9,532 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 8 WA * 15 |
ソースコード
#ifndef HIDDEN_IN_VS // 折りたたみ用
// 警告の抑制
#define _CRT_SECURE_NO_WARNINGS
// ライブラリの読み込み
#include <bits/stdc++.h>
using namespace std;
// 型名の短縮
using ll = long long; using ull = unsigned long long; // -2^63 ～ 2^63 = 9e18（int は -2^31 ～ 2^31 = 2e9）
using pii = pair<int, int>; using pll = pair<ll, ll>; using pil = pair<int, ll>; using pli = pair<ll, int>;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vvvvi = vector<vvvi>;
using vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>; using vvvvl = vector<vvvl>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vc = vector<char>; using vvc = vector<vc>; using vvvc = vector<vvc>;
using vd = vector<double>; using vvd = vector<vd>; using vvvd = vector<vvd>;
template <class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
using Graph = vvi;
// 定数の定義
const double PI = acos(-1);
int DX[4] = { 1, 0, -1, 0 }; // 4 近傍（下，右，上，左）
int DY[4] = { 0, 1, 0, -1 };
int INF = 1001001001; ll INFL = 4004004003094073385LL; // (int)INFL = INF, (int)(-INFL) = -INF;
// 入出力高速化
struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp;
// 汎用マクロの定義
#define all(a) (a).begin(), (a).end()
#define sz(x) ((int)(x).size())
#define lbpos(a, x) (int)distance((a).begin(), std::lower_bound(all(a), (x)))
#define ubpos(a, x) (int)distance((a).begin(), std::upper_bound(all(a), (x)))
#define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");}
#define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順
#define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順
#define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s から t まで降順
#define repe(v, a) for(const auto& v : (a)) // a の全要素（変更不可能）
#define repea(v, a) for(auto& v : (a)) // a の全要素（変更可能）
#define repb(set, d) for(int set = 0, set##_ub = 1 << int(d); set < set##_ub; ++set) // d ビット全探索（昇順）
#define repis(i, set) for(int i = lsb(set), bset##i = set; i < 32; bset##i -= 1 << i, i = lsb(bset##i)) // set の全要素（昇順）
#define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て（昇順）
#define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去
#define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了
#define inQ(x, y, u, l, d, r) ((u) <= (x) && (l) <= (y) && (x) < (d) && (y) < (r)) // 半開矩形内判定
// 汎用関数の定義
template <class T> inline ll powi(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; }
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新（更新されたら true を返す）
template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新（更新されたら true を返す）
template <class T> inline T getb(T set, int i) { return (set >> i) & T(1); }
template <class T> inline T smod(T n, T m) { n %= m; if (n < 0) n += m; return n; } // 非負mod
// 演算子オーバーロード
template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template <class T> inline istream& operator>>(istream& is, vector<T>& v) { repea(x, v) is >> x; return is; }
template <class T> inline vector<T>& operator--(vector<T>& v) { repea(x, v) --x; return v; }
template <class T> inline vector<T>& operator++(vector<T>& v) { repea(x, v) ++x; return v; }
#endif // 折りたたみ用
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#ifdef _MSC_VER
#include "localACL.hpp"
#endif
using mint = modint998244353;
//using mint = static_modint<(int)1e9+7>;
//using mint = modint; // mint::set_mod(m);
using vm = vector<mint>; using vvm = vector<vm>; using vvvm = vector<vvm>; using vvvvm = vector<vvvm>; using pim = pair<int, mint>;
#endif
#ifdef _MSC_VER // 手元環境（Visual Studio）
#include "local.hpp"
#else // 提出用（gcc）
int mute_dump = 0;
int frac_print = 0;
#if __has_include(<atcoder/all>)
namespace atcoder {
inline istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; }
inline ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; }
}
#endif
inline int popcount(int n) { return __builtin_popcount(n); }
inline int popcount(ll n) { return __builtin_popcountll(n); }
inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : 32; }
inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : 64; }
inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; }
inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; }
#define dump(...)
#define dumpel(v)
#define dump_math(v)
#define input_from_file(f)
#define output_to_file(f)
#define Assert(b) { if (!(b)) { vc MLE(1<<30); EXIT(MLE.back()); } } // RE の代わりに MLE を出す
#endif
//【幅優先探索】O(|V| + |E|)
/*
* グラフ g に対し，始点 st から各頂点 i への最短経路長を dist[i] に格納する．
* i が st から到達不能な頂点の場合は dist[i] = INF となる．
*/
template <class G> void breadth_first_search(const G& g, int st, vi& dist) {
// verify : https://algo-method.com/tasks/414
int n = sz(g);
dist = vi(n, INF); // スタートからの最短距離を保持するテーブル : O(n)
dist[st] = 0;
queue<int> que; // 次に探索する頂点を入れておくキュー
que.push(st);
while (!que.empty()) {
// 未探索の頂点を 1 つ得る．
auto s = que.front(); que.pop();
repe(t, g[s]) {
// 発見済みの頂点なら何もしない．
if (dist[t] != INF) continue;
// スタートからの最短距離を確定する．
// 幅優先探索なので，最短だという保証がある．
dist[t] = dist[s] + 1;
// 未探索の頂点として t を追加する．
que.push(t);
}
}
}
//【桁の数の取得】O(log n)
/*
* n を b 進表記したときの桁の数字を上位桁から順に並べたリストを返す．
*
* 制約：b ≧ 2
*/
vi integer_digits(ll n, int b = 10) {
// verify : https://atcoder.jp/contests/abc105/tasks/abc105_c
Assert(abs(b) >= 2);
// n = 0 の場合の例外処理
if (n == 0) return vi{ 0 };
// mod |b| を取れば最下位桁から順に決定していく．
vi ds;
while (n != 0) {
int d = (int)(n % b);
//int d = (int)smod(n, abs(b)); // 負数の可能性があるならこっち
ds.push_back(d);
n = (n - d) / b;
}
// 上位桁から順になるように並べ直す．
reverse(all(ds));
return ds;
}
// 愚直で学習用データを集める．
void zikken() {
int n = 1000;
Graph g(n);
rep(s, n) {
rep(i, 31) {
int t = s + (1 << i);
if (t >= n) break;
g[s].push_back(t);
}
rep(i, 31) {
int t = s - (1 << i);
if (t < 0) break;
g[s].push_back(t);
}
}
vi dist;
breadth_first_search(g, 0, dist);
repi(i, 1, n - 1) dist[i] += dist[i - 1];
// bit列 → 値
vector<pair<vi, ll>> data;
rep(i, n) {
auto res = dist[i];
auto ds = integer_digits(i, 2);
while (sz(ds) < 10) {
data.push_back({ ds, res });
ds.insert(ds.begin(), 0);
}
}
// 整形して出力
string out;
out += "data=Association[";
for (auto [key, val] : data) {
out += "{";
repe(d, key) out += to_string(d) + ",";
out.pop_back();
out += "}->" + to_string(val) + ",";
}
out.pop_back();
out += "];";
cout << out << endl;
exit(0);
}
/*
data=Association[{0}->0,{0,0}->0,{0,0,0}->0,{0,0,0,0}->0,{0,0,0,0,0}->0,{0,0,0,0,0,0}->0,{0,0,0,0,0,0,0}->0,{0,0,0,0,0,0,0,0}->0,{0,0,0,0,0,0,0,0,0}->0,{1}->1,{0,1}->1,{0,0,1}->1,{0,0,0,1}->1,{0,0,0,0,1}->1,{0,0,0,0,0,1}->1,{0,0,0,0,0,0,1}->1,{0,0,0,0,0,0,0,1}->1,{0,0,0,0,0,0,0,0,1}->1,{1,0}->2,{0,1,0}->2,{0,0,1,0}->2,{0,0,0,1,0}->2,{0,0,0,0,1,0}->2,{0,0,0,0,0,1,0}->2,{0,0,0,0,0,0,1,0}->2,{0,0,0,0,0,0,0,1,0}->2,{1,1}->4,{0,1,1}->4,{0,0,1,1}->4,{0,0,0,1,1}->4,{0,0,0,0,1,1}->4,{0,0,0,0,0,1,1}->4,{0,0,0,0,0,0,1,1}->4,{0,0,0,0,0,0,0,1,1}->4,{1,0,0}->5,{0,1,0,0}->5,{0,0,1,0,0}->5,{0,0,0,1,0,0}->5,{0,0,0,0,1,0,0}->5,{0,0,0,0,0,1,0,0}->5,{0,0,0,0,0,0,1,0,0}->5,{1,0,1}->7,{0,1,0,1}->7,{0,0,1,0,1}->7,{0,0,0,1,0,1}->7,{0,0,0,0,1,0,1}->7,{0,0,0,0,0,1,0,1}->7,{0,0,0,0,0,0,1,0,1}->7,{1,1,0}->9,{0,1,1,0}->9,{0,0,1,1,0}->9,{0,0,0,1,1,0}->9,{0,0,0,0,1,1,0}->9,{0,0,0,0,0,1,1,0}->9,{0,0,0,0,0,0,1,1,0}->9,{1,1,1}->11,{0,1,1,1}->11,{0,0,1,1,1}->11,{0,0,0,1,1,1}->11,{0,0,0,0,1,1,1}->11,{0,0,0,0,0,1,1,1}->11,{0,0,0,0,0,0,1,1,1}->11,{1,0,0,0}->12,{0,1,0,0,0}->12,{0,0,1,0,0,0}->12,{0,0,0,1,0,0,0}->12,{0,0,0,0,1,0,0,0}->12,{0,0,0,0,0,1,0,0,0}->12,{1,0,0,1}->14,{0,1,0,0,1}->14,{0,0,1,0,0,1}->14,{0,0,0,1,0,0,1}->14,{0,0,0,0,1,0,0,1}->14,{0,0,0,0,0,1,0,0,1}->14,{1,0,1,0}->16,{0,1,0,1,0}->16,{0,0,1,0,1,0}->16,{0,0,0,1,0,1,0}->16,{0,0,0,0,1,0,1,0}->16,{0,0,0,0,0,1,0,1,0}->16,{1,0,1,1}->19,{0,1,0,1,1}->19,{0,0,1,0,1,1}->19,{0,0,0,1,0,1,1}->19,{0,0,0,0,1,0,1,1}->19,{0,0,0,0,0,1,0,1,1}->19,{1,1,0,0}->21,{0,1,1,0,0}->21,{0,0,1,1,0,0}->21,{0,0,0,1,1,0,0}->21,{0,0,0,0,1,1,0,0}->21,{0,0,0,0,0,1,1,0,0}->21,{1,1,0,1}->24,{0,1,1,0,1}->24,{0,0,1,1,0,1}->24,{0,0,0,1,1,0,1}->24,{0,0,0,0,1,1,0,1}->24,{0,0,0,0,0,1,1,0,1}->24,{1,1,1,0}->26,{0,1,1,1,0}->26,{0,0,1,1,1,0}->26,{0,0,0,1,1,1,0}->26,{0,0,0,0,1,1,1,0}->26,{0,0,0,0,0,1,1,1,0}->26,{1,1,1,1}->28,{0,1,1,1,1}->28,{0,0,1,1,1,1}->28,{0,0,0,1,1,1,1}->28,{0,0,0,0,1,1,1,1}->28,{0,0,0,0,0,1,1,1,1}->28,{1,0,0,0,0}->29,{0,1,0,0,0,0}->29,{0,0,1,0,0,0,0}->29,{0,0,0,1,0,0,0,0}->29,{0,0,0,0,1,0,0,0,0}->29,{1,0,0,0,1}->31,{0,1,0,0,0,1}->31,{0,0,1,0,0,0,1}->31,{0,0,0,1,0,0,0,1}->31,{0,0,0,0,1,0,0,0,1}->31,{1,0,0,1,0}->33,{0,1,0,0,1,0}->33,{0,0,1,0,0,1,0}->33,{0,0,0,1,0,0,1,0}->33,{0,0,0,0,1,0,0,1,0}->33,{1,0,0,1,1}->36,{0,1,0,0,1,1}->36,{0,0,1,0,0,1,1}->36,{0,0,0,1,0,0,1,1}->36,{0,0,0,0,1,0,0,1,1}->36,{1,0,1,0,0}->38,{0,1,0,1,0,0}->38,{0,0,1,0,1,0,0}->38,{0,0,0,1,0,1,0,0}->38,{0,0,0,0,1,0,1,0,0}->38,{1,0,1,0,1}->41,{0,1,0,1,0,1}->41,{0,0,1,0,1,0,1}->41,{0,0,0,1,0,1,0,1}->41,{0,0,0,0,1,0,1,0,1}->41,{1,0,1,1,0}->44,{0,1,0,1,1,0}->44,{0,0,1,0,1,1,0}->44,{0,0,0,1,0,1,1,0}->44,{0,0,0,0,1,0,1,1,0}->44,{1,0,1,1,1}->47,{0,1,0,1,1,1}->47,{0,0,1,0,1,1,1}->47,{0,0,0,1,0,1,1,1}->47,{0,0,0,0,1,0,1,1,1}->47,{1,1,0,0,0}->49,{0,1,1,0,0,0}->49,{0,0,1,1,0,0,0}->49,{0,0,0,1,1,0,0,0}->49,{0,0,0,0,1,1,0,0,0}->49,{1,1,0,0,1}->52,{0,1,1,0,0,1}->52,{0,0,1,1,0,0,1}->52,{0,0,0,1,1,0,0,1}->52,{0,0,0,0,1,1,0,0,1}->52,{1,1,0,1,0}->55,{0,1,1,0,1,0}->55,{0,0,1,1,0,1,0}->55,{0,0,0,1,1,0,1,0}->55,{0,0,0,0,1,1,0,1,0}->55,{1,1,0,1,1}->58,{0,1,1,0,1,1}->58,{0,0,1,1,0,1,1}->58,{0,0,0,1,1,0,1,1}->58,{0,0,0,0,1,1,0,1,1}->58,{1,1,1,0,0}->60,{0,1,1,1,0,0}->60,{0,0,1,1,1,0,0}->60,{0,0,0,1,1,1,0,0}->60,{0,0,0,0,1,1,1,0,0}->60,{1,1,1,0,1}->63,{0,1,1,1,0,1}->63,{0,0,1,1,1,0,1}->63,{0,0,0,1,1,1,0,1}->63,{0,0,0,0,1,1,1,0,1}->63,{1,1,1,1,0}->65,{0,1,1,1,1,0}->65,{0,0,1,1,1,1,0}->65,{0,0,0,1,1,1,1,0}->65,{0,0,0,0,1,1,1,1,0}->65,{1,1,1,1,1}->67,{0,1,1,1,1,1}->67,{0,0,1,1,1,1,1}->67,{0,0,0,1,1,1,1,1}->67,{0,0,0,0,1,1,1,1,1}->67,{1,0,0,0,0,0}->68,{0,1,0,0,0,0,0}->68,{0,0,1,0,0,0,0,0}->68,{0,0,0,1,0,0,0,0,0}->68,{1,0,0,0,0,1}->70,{0,1,0,0,0,0,1}->70,{0,0,1,0,0,0,0,1}->70,{0,0,0,1,0,0,0,0,1}->70,{1,0,0,0,1,0}->72,{0,1,0,0,0,1,0}->72,{0,0,1,0,0,0,1,0}->72,{0,0,0,1,0,0,0,1,0}->72,{1,0,0,0,1,1}->75,{0,1,0,0,0,1,1}->75,{0,0,1,0,0,0,1,1}->75,{0,0,0,1,0,0,0,1,1}->75,{1,0,0,1,0,0}->77,{0,1,0,0,1,0,0}->77,{0,0,1,0,0,1,0,0}->77,{0,0,0,1,0,0,1,0,0}->77,{1,0,0,1,0,1}->80,{0,1,0,0,1,0,1}->80,{0,0,1,0,0,1,0,1}->80,{0,0,0,1,0,0,1,0,1}->80,{1,0,0,1,1,0}->83,{0,1,0,0,1,1,0}->83,{0,0,1,0,0,1,1,0}->83,{0,0,0,1,0,0,1,1,0}->83,{1,0,0,1,1,1}->86,{0,1,0,0,1,1,1}->86,{0,0,1,0,0,1,1,1}->86,{0,0,0,1,0,0,1,1,1}->86,{1,0,1,0,0,0}->88,{0,1,0,1,0,0,0}->88,{0,0,1,0,1,0,0,0}->88,{0,0,0,1,0,1,0,0,0}->88,{1,0,1,0,0,1}->91,{0,1,0,1,0,0,1}->91,{0,0,1,0,1,0,0,1}->91,{0,0,0,1,0,1,0,0,1}->91,{1,0,1,0,1,0}->94,{0,1,0,1,0,1,0}->94,{0,0,1,0,1,0,1,0}->94,{0,0,0,1,0,1,0,1,0}->94,{1,0,1,0,1,1}->98,{0,1,0,1,0,1,1}->98,{0,0,1,0,1,0,1,1}->98,{0,0,0,1,0,1,0,1,1}->98,{1,0,1,1,0,0}->101,{0,1,0,1,1,0,0}->101,{0,0,1,0,1,1,0,0}->101,{0,0,0,1,0,1,1,0,0}->101,{1,0,1,1,0,1}->105,{0,1,0,1,1,0,1}->105,{0,0,1,0,1,1,0,1}->105,{0,0,0,1,0,1,1,0,1}->105,{1,0,1,1,1,0}->108,{0,1,0,1,1,1,0}->108,{0,0,1,0,1,1,1,0}->108,{0,0,0,1,0,1,1,1,0}->108,{1,0,1,1,1,1}->111,{0,1,0,1,1,1,1}->111,{0,0,1,0,1,1,1,1}->111,{0,0,0,1,0,1,1,1,1}->111,{1,1,0,0,0,0}->113,{0,1,1,0,0,0,0}->113,{0,0,1,1,0,0,0,0}->113,{0,0,0,1,1,0,0,0,0}->113,{1,1,0,0,0,1}->116,{0,1,1,0,0,0,1}->116,{0,0,1,1,0,0,0,1}->116,{0,0,0,1,1,0,0,0,1}->116,{1,1,0,0,1,0}->119,{0,1,1,0,0,1,0}->119,{0,0,1,1,0,0,1,0}->119,{0,0,0,1,1,0,0,1,0}->119,{1,1,0,0,1,1}->123,{0,1,1,0,0,1,1}->123,{0,0,1,1,0,0,1,1}->123,{0,0,0,1,1,0,0,1,1}->123,{1,1,0,1,0,0}->126,{0,1,1,0,1,0,0}->126,{0,0,1,1,0,1,0,0}->126,{0,0,0,1,1,0,1,0,0}->126,{1,1,0,1,0,1}->130,{0,1,1,0,1,0,1}->130,{0,0,1,1,0,1,0,1}->130,{0,0,0,1,1,0,1,0,1}->130,{1,1,0,1,1,0}->133,{0,1,1,0,1,1,0}->133,{0,0,1,1,0,1,1,0}->133,{0,0,0,1,1,0,1,1,0}->133,{1,1,0,1,1,1}->136,{0,1,1,0,1,1,1}->136,{0,0,1,1,0,1,1,1}->136,{0,0,0,1,1,0,1,1,1}->136,{1,1,1,0,0,0}->138,{0,1,1,1,0,0,0}->138,{0,0,1,1,1,0,0,0}->138,{0,0,0,1,1,1,0,0,0}->138,{1,1,1,0,0,1}->141,{0,1,1,1,0,0,1}->141,{0,0,1,1,1,0,0,1}->141,{0,0,0,1,1,1,0,0,1}->141,{1,1,1,0,1,0}->144,{0,1,1,1,0,1,0}->144,{0,0,1,1,1,0,1,0}->144,{0,0,0,1,1,1,0,1,0}->144,{1,1,1,0,1,1}->147,{0,1,1,1,0,1,1}->147,{0,0,1,1,1,0,1,1}->147,{0,0,0,1,1,1,0,1,1}->147,{1,1,1,1,0,0}->149,{0,1,1,1,1,0,0}->149,{0,0,1,1,1,1,0,0}->149,{0,0,0,1,1,1,1,0,0}->149,{1,1,1,1,0,1}->152,{0,1,1,1,1,0,1}->152,{0,0,1,1,1,1,0,1}->152,{0,0,0,1,1,1,1,0,1}->152,{1,1,1,1,1,0}->154,{0,1,1,1,1,1,0}->154,{0,0,1,1,1,1,1,0}->154,{0,0,0,1,1,1,1,1,0}->154,{1,1,1,1,1,1}->156,{0,1,1,1,1,1,1}->156,{0,0,1,1,1,1,1,1}->156,{0,0,0,1,1,1,1,1,1}->156,{1,0,0,0,0,0,0}->157,{0,1,0,0,0,0,0,0}->157,{0,0,1,0,0,0,0,0,0}->157,{1,0,0,0,0,0,1}->159,{0,1,0,0,0,0,0,1}->159,{0,0,1,0,0,0,0,0,1}->159,{1,0,0,0,0,1,0}->161,{0,1,0,0,0,0,1,0}->161,{0,0,1,0,0,0,0,1,0}->161,{1,0,0,0,0,1,1}->164,{0,1,0,0,0,0,1,1}->164,{0,0,1,0,0,0,0,1,1}->164,{1,0,0,0,1,0,0}->166,{0,1,0,0,0,1,0,0}->166,{0,0,1,0,0,0,1,0,0}->166,{1,0,0,0,1,0,1}->169,{0,1,0,0,0,1,0,1}->169,{0,0,1,0,0,0,1,0,1}->169,{1,0,0,0,1,1,0}->172,{0,1,0,0,0,1,1,0}->172,{0,0,1,0,0,0,1,1,0}->172,{1,0,0,0,1,1,1}->175,{0,1,0,0,0,1,1,1}->175,{0,0,1,0,0,0,1,1,1}->175,{1,0,0,1,0,0,0}->177,{0,1,0,0,1,0,0,0}->177,{0,0,1,0,0,1,0,0,0}->177,{1,0,0,1,0,0,1}->180,{0,1,0,0,1,0,0,1}->180,{0,0,1,0,0,1,0,0,1}->180,{1,0,0,1,0,1,0}->183,{0,1,0,0,1,0,1,0}->183,{0,0,1,0,0,1,0,1,0}->183,{1,0,0,1,0,1,1}->187,{0,1,0,0,1,0,1,1}->187,{0,0,1,0,0,1,0,1,1}->187,{1,0,0,1,1,0,0}->190,{0,1,0,0,1,1,0,0}->190,{0,0,1,0,0,1,1,0,0}->190,{1,0,0,1,1,0,1}->194,{0,1,0,0,1,1,0,1}->194,{0,0,1,0,0,1,1,0,1}->194,{1,0,0,1,1,1,0}->197,{0,1,0,0,1,1,1,0}->197,{0,0,1,0,0,1,1,1,0}->197,{1,0,0,1,1,1,1}->200,{0,1,0,0,1,1,1,1}->200,{0,0,1,0,0,1,1,1,1}->200,{1,0,1,0,0,0,0}->202,{0,1,0,1,0,0,0,0}->202,{0,0,1,0,1,0,0,0,0}->202,{1,0,1,0,0,0,1}->205,{0,1,0,1,0,0,0,1}->205,{0,0,1,0,1,0,0,0,1}->205,{1,0,1,0,0,1,0}->208,{0,1,0,1,0,0,1,0}->208,{0,0,1,0,1,0,0,1,0}->208,{1,0,1,0,0,1,1}->212,{0,1,0,1,0,0,1,1}->212,{0,0,1,0,1,0,0,1,1}->212,{1,0,1,0,1,0,0}->215,{0,1,0,1,0,1,0,0}->215,{0,0,1,0,1,0,1,0,0}->215,{1,0,1,0,1,0,1}->219,{0,1,0,1,0,1,0,1}->219,{0,0,1,0,1,0,1,0,1}->219,{1,0,1,0,1,1,0}->223,{0,1,0,1,0,1,1,0}->223,{0,0,1,0,1,0,1,1,0}->223,{1,0,1,0,1,1,1}->227,{0,1,0,1,0,1,1,1}->227,{0,0,1,0,1,0,1,1,1}->227,{1,0,1,1,0,0,0}->230,{0,1,0,1,1,0,0,0}->230,{0,0,1,0,1,1,0,0,0}->230,{1,0,1,1,0,0,1}->234,{0,1,0,1,1,0,0,1}->234,{0,0,1,0,1,1,0,0,1}->234,{1,0,1,1,0,1,0}->238,{0,1,0,1,1,0,1,0}->238,{0,0,1,0,1,1,0,1,0}->238,{1,0,1,1,0,1,1}->242,{0,1,0,1,1,0,1,1}->242,{0,0,1,0,1,1,0,1,1}->242,{1,0,1,1,1,0,0}->245,{0,1,0,1,1,1,0,0}->245,{0,0,1,0,1,1,1,0,0}->245,{1,0,1,1,1,0,1}->249,{0,1,0,1,1,1,0,1}->249,{0,0,1,0,1,1,1,0,1}->249,{1,0,1,1,1,1,0}->252,{0,1,0,1,1,1,1,0}->252,{0,0,1,0,1,1,1,1,0}->252,{1,0,1,1,1,1,1}->255,{0,1,0,1,1,1,1,1}->255,{0,0,1,0,1,1,1,1,1}->255,{1,1,0,0,0,0,0}->257,{0,1,1,0,0,0,0,0}->257,{0,0,1,1,0,0,0,0,0}->257,{1,1,0,0,0,0,1}->260,{0,1,1,0,0,0,0,1}->260,{0,0,1,1,0,0,0,0,1}->260,{1,1,0,0,0,1,0}->263,{0,1,1,0,0,0,1,0}->263,{0,0,1,1,0,0,0,1,0}->263,{1,1,0,0,0,1,1}->267,{0,1,1,0,0,0,1,1}->267,{0,0,1,1,0,0,0,1,1}->267,{1,1,0,0,1,0,0}->270,{0,1,1,0,0,1,0,0}->270,{0,0,1,1,0,0,1,0,0}->270,{1,1,0,0,1,0,1}->274,{0,1,1,0,0,1,0,1}->274,{0,0,1,1,0,0,1,0,1}->274,{1,1,0,0,1,1,0}->278,{0,1,1,0,0,1,1,0}->278,{0,0,1,1,0,0,1,1,0}->278,{1,1,0,0,1,1,1}->282,{0,1,1,0,0,1,1,1}->282,{0,0,1,1,0,0,1,1,1}->282,{1,1,0,1,0,0,0}->285,{0,1,1,0,1,0,0,0}->285,{0,0,1,1,0,1,0,0,0}->285,{1,1,0,1,0,0,1}->289,{0,1,1,0,1,0,0,1}->289,{0,0,1,1,0,1,0,0,1}->289,{1,1,0,1,0,1,0}->293,{0,1,1,0,1,0,1,0}->293,{0,0,1,1,0,1,0,1,0}->293,{1,1,0,1,0,1,1}->297,{0,1,1,0,1,0,1,1}->297,{0,0,1,1,0,1,0,1,1}->297,{1,1,0,1,1,0,0}->300,{0,1,1,0,1,1,0,0}->300,{0,0,1,1,0,1,1,0,0}->300,{1,1,0,1,1,0,1}->304,{0,1,1,0,1,1,0,1}->304,{0,0,1,1,0,1,1,0,1}->304,{1,1,0,1,1,1,0}->307,{0,1,1,0,1,1,1,0}->307,{0,0,1,1,0,1,1,1,0}->307,{1,1,0,1,1,1,1}->310,{0,1,1,0,1,1,1,1}->310,{0,0,1,1,0,1,1,1,1}->310,{1,1,1,0,0,0,0}->312,{0,1,1,1,0,0,0,0}->312,{0,0,1,1,1,0,0,0,0}->312,{1,1,1,0,0,0,1}->315,{0,1,1,1,0,0,0,1}->315,{0,0,1,1,1,0,0,0,1}->315,{1,1,1,0,0,1,0}->318,{0,1,1,1,0,0,1,0}->318,{0,0,1,1,1,0,0,1,0}->318,{1,1,1,0,0,1,1}->322,{0,1,1,1,0,0,1,1}->322,{0,0,1,1,1,0,0,1,1}->322,{1,1,1,0,1,0,0}->325,{0,1,1,1,0,1,0,0}->325,{0,0,1,1,1,0,1,0,0}->325,{1,1,1,0,1,0,1}->329,{0,1,1,1,0,1,0,1}->329,{0,0,1,1,1,0,1,0,1}->329,{1,1,1,0,1,1,0}->332,{0,1,1,1,0,1,1,0}->332,{0,0,1,1,1,0,1,1,0}->332,{1,1,1,0,1,1,1}->335,{0,1,1,1,0,1,1,1}->335,{0,0,1,1,1,0,1,1,1}->335,{1,1,1,1,0,0,0}->337,{0,1,1,1,1,0,0,0}->337,{0,0,1,1,1,1,0,0,0}->337,{1,1,1,1,0,0,1}->340,{0,1,1,1,1,0,0,1}->340,{0,0,1,1,1,1,0,0,1}->340,{1,1,1,1,0,1,0}->343,{0,1,1,1,1,0,1,0}->343,{0,0,1,1,1,1,0,1,0}->343,{1,1,1,1,0,1,1}->346,{0,1,1,1,1,0,1,1}->346,{0,0,1,1,1,1,0,1,1}->346,{1,1,1,1,1,0,0}->348,{0,1,1,1,1,1,0,0}->348,{0,0,1,1,1,1,1,0,0}->348,{1,1,1,1,1,0,1}->351,{0,1,1,1,1,1,0,1}->351,{0,0,1,1,1,1,1,0,1}->351,{1,1,1,1,1,1,0}->353,{0,1,1,1,1,1,1,0}->353,{0,0,1,1,1,1,1,1,0}->353,{1,1,1,1,1,1,1}->355,{0,1,1,1,1,1,1,1}->355,{0,0,1,1,1,1,1,1,1}->355,{1,0,0,0,0,0,0,0}->356,{0,1,0,0,0,0,0,0,0}->356,{1,0,0,0,0,0,0,1}->358,{0,1,0,0,0,0,0,0,1}->358,{1,0,0,0,0,0,1,0}->360,{0,1,0,0,0,0,0,1,0}->360,{1,0,0,0,0,0,1,1}->363,{0,1,0,0,0,0,0,1,1}->363,{1,0,0,0,0,1,0,0}->365,{0,1,0,0,0,0,1,0,0}->365,{1,0,0,0,0,1,0,1}->368,{0,1,0,0,0,0,1,0,1}->368,{1,0,0,0,0,1,1,0}->371,{0,1,0,0,0,0,1,1,0}->371,{1,0,0,0,0,1,1,1}->374,{0,1,0,0,0,0,1,1,1}->374,{1,0,0,0,1,0,0,0}->376,{0,1,0,0,0,1,0,0,0}->376,{1,0,0,0,1,0,0,1}->379,{0,1,0,0,0,1,0,0,1}->379,{1,0,0,0,1,0,1,0}->382,{0,1,0,0,0,1,0,1,0}->382,{1,0,0,0,1,0,1,1}->386,{0,1,0,0,0,1,0,1,1}->386,{1,0,0,0,1,1,0,0}->389,{0,1,0,0,0,1,1,0,0}->389,{1,0,0,0,1,1,0,1}->393,{0,1,0,0,0,1,1,0,1}->393,{1,0,0,0,1,1,1,0}->396,{0,1,0,0,0,1,1,1,0}->396,{1,0,0,0,1,1,1,1}->399,{0,1,0,0,0,1,1,1,1}->399,{1,0,0,1,0,0,0,0}->401,{0,1,0,0,1,0,0,0,0}->401,{1,0,0,1,0,0,0,1}->404,{0,1,0,0,1,0,0,0,1}->404,{1,0,0,1,0,0,1,0}->407,{0,1,0,0,1,0,0,1,0}->407,{1,0,0,1,0,0,1,1}->411,{0,1,0,0,1,0,0,1,1}->411,{1,0,0,1,0,1,0,0}->414,{0,1,0,0,1,0,1,0,0}->414,{1,0,0,1,0,1,0,1}->418,{0,1,0,0,1,0,1,0,1}->418,{1,0,0,1,0,1,1,0}->422,{0,1,0,0,1,0,1,1,0}->422,{1,0,0,1,0,1,1,1}->426,{0,1,0,0,1,0,1,1,1}->426,{1,0,0,1,1,0,0,0}->429,{0,1,0,0,1,1,0,0,0}->429,{1,0,0,1,1,0,0,1}->433,{0,1,0,0,1,1,0,0,1}->433,{1,0,0,1,1,0,1,0}->437,{0,1,0,0,1,1,0,1,0}->437,{1,0,0,1,1,0,1,1}->441,{0,1,0,0,1,1,0,1,1}->441,{1,0,0,1,1,1,0,0}->444,{0,1,0,0,1,1,1,0,0}->444,{1,0,0,1,1,1,0,1}->448,{0,1,0,0,1,1,1,0,1}->448,{1,0,0,1,1,1,1,0}->451,{0,1,0,0,1,1,1,1,0}->451,{1,0,0,1,1,1,1,1}->454,{0,1,0,0,1,1,1,1,1}->454,{1,0,1,0,0,0,0,0}->456,{0,1,0,1,0,0,0,0,0}->456,{1,0,1,0,0,0,0,1}->459,{0,1,0,1,0,0,0,0,1}->459,{1,0,1,0,0,0,1,0}->462,{0,1,0,1,0,0,0,1,0}->462,{1,0,1,0,0,0,1,1}->466,{0,1,0,1,0,0,0,1,1}->466,{1,0,1,0,0,1,0,0}->469,{0,1,0,1,0,0,1,0,0}->469,{1,0,1,0,0,1,0,1}->473,{0,1,0,1,0,0,1,0,1}->473,{1,0,1,0,0,1,1,0}->477,{0,1,0,1,0,0,1,1,0}->477,{1,0,1,0,0,1,1,1}->481,{0,1,0,1,0,0,1,1,1}->481,{1,0,1,0,1,0,0,0}->484,{0,1,0,1,0,1,0,0,0}->484,{1,0,1,0,1,0,0,1}->488,{0,1,0,1,0,1,0,0,1}->488,{1,0,1,0,1,0,1,0}->492,{0,1,0,1,0,1,0,1,0}->492,{1,0,1,0,1,0,1,1}->497,{0,1,0,1,0,1,0,1,1}->497,{1,0,1,0,1,1,0,0}->501,{0,1,0,1,0,1,1,0,0}->501,{1,0,1,0,1,1,0,1}->506,{0,1,0,1,0,1,1,0,1}->506,{1,0,1,0,1,1,1,0}->510,{0,1,0,1,0,1,1,1,0}->510,{1,0,1,0,1,1,1,1}->514,{0,1,0,1,0,1,1,1,1}->514,{1,0,1,1,0,0,0,0}->517,{0,1,0,1,1,0,0,0,0}->517,{1,0,1,1,0,0,0,1}->521,{0,1,0,1,1,0,0,0,1}->521,{1,0,1,1,0,0,1,0}->525,{0,1,0,1,1,0,0,1,0}->525,{1,0,1,1,0,0,1,1}->530,{0,1,0,1,1,0,0,1,1}->530,{1,0,1,1,0,1,0,0}->534,{0,1,0,1,1,0,1,0,0}->534,{1,0,1,1,0,1,0,1}->539,{0,1,0,1,1,0,1,0,1}->539,{1,0,1,1,0,1,1,0}->543,{0,1,0,1,1,0,1,1,0}->543,{1,0,1,1,0,1,1,1}->547,{0,1,0,1,1,0,1,1,1}->547,{1,0,1,1,1,0,0,0}->550,{0,1,0,1,1,1,0,0,0}->550,{1,0,1,1,1,0,0,1}->554,{0,1,0,1,1,1,0,0,1}->554,{1,0,1,1,1,0,1,0}->558,{0,1,0,1,1,1,0,1,0}->558,{1,0,1,1,1,0,1,1}->562,{0,1,0,1,1,1,0,1,1}->562,{1,0,1,1,1,1,0,0}->565,{0,1,0,1,1,1,1,0,0}->565,{1,0,1,1,1,1,0,1}->569,{0,1,0,1,1,1,1,0,1}->569,{1,0,1,1,1,1,1,0}->572,{0,1,0,1,1,1,1,1,0}->572,{1,0,1,1,1,1,1,1}->575,{0,1,0,1,1,1,1,1,1}->575,{1,1,0,0,0,0,0,0}->577,{0,1,1,0,0,0,0,0,0}->577,{1,1,0,0,0,0,0,1}->580,{0,1,1,0,0,0,0,0,1}->580,{1,1,0,0,0,0,1,0}->583,{0,1,1,0,0,0,0,1,0}->583,{1,1,0,0,0,0,1,1}->587,{0,1,1,0,0,0,0,1,1}->587,{1,1,0,0,0,1,0,0}->590,{0,1,1,0,0,0,1,0,0}->590,{1,1,0,0,0,1,0,1}->594,{0,1,1,0,0,0,1,0,1}->594,{1,1,0,0,0,1,1,0}->598,{0,1,1,0,0,0,1,1,0}->598,{1,1,0,0,0,1,1,1}->602,{0,1,1,0,0,0,1,1,1}->602,{1,1,0,0,1,0,0,0}->605,{0,1,1,0,0,1,0,0,0}->605,{1,1,0,0,1,0,0,1}->609,{0,1,1,0,0,1,0,0,1}->609,{1,1,0,0,1,0,1,0}->613,{0,1,1,0,0,1,0,1,0}->613,{1,1,0,0,1,0,1,1}->618,{0,1,1,0,0,1,0,1,1}->618,{1,1,0,0,1,1,0,0}->622,{0,1,1,0,0,1,1,0,0}->622,{1,1,0,0,1,1,0,1}->627,{0,1,1,0,0,1,1,0,1}->627,{1,1,0,0,1,1,1,0}->631,{0,1,1,0,0,1,1,1,0}->631,{1,1,0,0,1,1,1,1}->635,{0,1,1,0,0,1,1,1,1}->635,{1,1,0,1,0,0,0,0}->638,{0,1,1,0,1,0,0,0,0}->638,{1,1,0,1,0,0,0,1}->642,{0,1,1,0,1,0,0,0,1}->642,{1,1,0,1,0,0,1,0}->646,{0,1,1,0,1,0,0,1,0}->646,{1,1,0,1,0,0,1,1}->651,{0,1,1,0,1,0,0,1,1}->651,{1,1,0,1,0,1,0,0}->655,{0,1,1,0,1,0,1,0,0}->655,{1,1,0,1,0,1,0,1}->660,{0,1,1,0,1,0,1,0,1}->660,{1,1,0,1,0,1,1,0}->664,{0,1,1,0,1,0,1,1,0}->664,{1,1,0,1,0,1,1,1}->668,{0,1,1,0,1,0,1,1,1}->668,{1,1,0,1,1,0,0,0}->671,{0,1,1,0,1,1,0,0,0}->671,{1,1,0,1,1,0,0,1}->675,{0,1,1,0,1,1,0,0,1}->675,{1,1,0,1,1,0,1,0}->679,{0,1,1,0,1,1,0,1,0}->679,{1,1,0,1,1,0,1,1}->683,{0,1,1,0,1,1,0,1,1}->683,{1,1,0,1,1,1,0,0}->686,{0,1,1,0,1,1,1,0,0}->686,{1,1,0,1,1,1,0,1}->690,{0,1,1,0,1,1,1,0,1}->690,{1,1,0,1,1,1,1,0}->693,{0,1,1,0,1,1,1,1,0}->693,{1,1,0,1,1,1,1,1}->696,{0,1,1,0,1,1,1,1,1}->696,{1,1,1,0,0,0,0,0}->698,{0,1,1,1,0,0,0,0,0}->698,{1,1,1,0,0,0,0,1}->701,{0,1,1,1,0,0,0,0,1}->701,{1,1,1,0,0,0,1,0}->704,{0,1,1,1,0,0,0,1,0}->704,{1,1,1,0,0,0,1,1}->708,{0,1,1,1,0,0,0,1,1}->708,{1,1,1,0,0,1,0,0}->711,{0,1,1,1,0,0,1,0,0}->711,{1,1,1,0,0,1,0,1}->715,{0,1,1,1,0,0,1,0,1}->715,{1,1,1,0,0,1,1,0}->719,{0,1,1,1,0,0,1,1,0}->719,{1,1,1,0,0,1,1,1}->723,{0,1,1,1,0,0,1,1,1}->723,{1,1,1,0,1,0,0,0}->726,{0,1,1,1,0,1,0,0,0}->726,{1,1,1,0,1,0,0,1}->730,{0,1,1,1,0,1,0,0,1}->730,{1,1,1,0,1,0,1,0}->734,{0,1,1,1,0,1,0,1,0}->734,{1,1,1,0,1,0,1,1}->738,{0,1,1,1,0,1,0,1,1}->738,{1,1,1,0,1,1,0,0}->741,{0,1,1,1,0,1,1,0,0}->741,{1,1,1,0,1,1,0,1}->745,{0,1,1,1,0,1,1,0,1}->745,{1,1,1,0,1,1,1,0}->748,{0,1,1,1,0,1,1,1,0}->748,{1,1,1,0,1,1,1,1}->751,{0,1,1,1,0,1,1,1,1}->751,{1,1,1,1,0,0,0,0}->753,{0,1,1,1,1,0,0,0,0}->753,{1,1,1,1,0,0,0,1}->756,{0,1,1,1,1,0,0,0,1}->756,{1,1,1,1,0,0,1,0}->759,{0,1,1,1,1,0,0,1,0}->759,{1,1,1,1,0,0,1,1}->763,{0,1,1,1,1,0,0,1,1}->763,{1,1,1,1,0,1,0,0}->766,{0,1,1,1,1,0,1,0,0}->766,{1,1,1,1,0,1,0,1}->770,{0,1,1,1,1,0,1,0,1}->770,{1,1,1,1,0,1,1,0}->773,{0,1,1,1,1,0,1,1,0}->773,{1,1,1,1,0,1,1,1}->776,{0,1,1,1,1,0,1,1,1}->776,{1,1,1,1,1,0,0,0}->778,{0,1,1,1,1,1,0,0,0}->778,{1,1,1,1,1,0,0,1}->781,{0,1,1,1,1,1,0,0,1}->781,{1,1,1,1,1,0,1,0}->784,{0,1,1,1,1,1,0,1,0}->784,{1,1,1,1,1,0,1,1}->787,{0,1,1,1,1,1,0,1,1}->787,{1,1,1,1,1,1,0,0}->789,{0,1,1,1,1,1,1,0,0}->789,{1,1,1,1,1,1,0,1}->792,{0,1,1,1,1,1,1,0,1}->792,{1,1,1,1,1,1,1,0}->794,{0,1,1,1,1,1,1,1,0}->794,{1,1,1,1,1,1,1,1}->796,{0,1,1,1,1,1,1,1,1}->796,{1,0,0,0,0,0,0,0,0}->797,{1,0,0,0,0,0,0,0,1}->799,{1,0,0,0,0,0,0,1,0}->801,{1,0,0,0,0,0,0,1,1}->804,{1,0,0,0,0,0,1,0,0}->806,{1,0,0,0,0,0,1,0,1}->809,{1,0,0,0,0,0,1,1,0}->812,{1,0,0,0,0,0,1,1,1}->815,{1,0,0,0,0,1,0,0,0}->817,{1,0,0,0,0,1,0,0,1}->820,{1,0,0,0,0,1,0,1,0}->823,{1,0,0,0,0,1,0,1,1}->827,{1,0,0,0,0,1,1,0,0}->830,{1,0,0,0,0,1,1,0,1}->834,{1,0,0,0,0,1,1,1,0}->837,{1,0,0,0,0,1,1,1,1}->840,{1,0,0,0,1,0,0,0,0}->842,{1,0,0,0,1,0,0,0,1}->845,{1,0,0,0,1,0,0,1,0}->848,{1,0,0,0,1,0,0,1,1}->852,{1,0,0,0,1,0,1,0,0}->855,{1,0,0,0,1,0,1,0,1}->859,{1,0,0,0,1,0,1,1,0}->863,{1,0,0,0,1,0,1,1,1}->867,{1,0,0,0,1,1,0,0,0}->870,{1,0,0,0,1,1,0,0,1}->874,{1,0,0,0,1,1,0,1,0}->878,{1,0,0,0,1,1,0,1,1}->882,{1,0,0,0,1,1,1,0,0}->885,{1,0,0,0,1,1,1,0,1}->889,{1,0,0,0,1,1,1,1,0}->892,{1,0,0,0,1,1,1,1,1}->895,{1,0,0,1,0,0,0,0,0}->897,{1,0,0,1,0,0,0,0,1}->900,{1,0,0,1,0,0,0,1,0}->903,{1,0,0,1,0,0,0,1,1}->907,{1,0,0,1,0,0,1,0,0}->910,{1,0,0,1,0,0,1,0,1}->914,{1,0,0,1,0,0,1,1,0}->918,{1,0,0,1,0,0,1,1,1}->922,{1,0,0,1,0,1,0,0,0}->925,{1,0,0,1,0,1,0,0,1}->929,{1,0,0,1,0,1,0,1,0}->933,{1,0,0,1,0,1,0,1,1}->938,{1,0,0,1,0,1,1,0,0}->942,{1,0,0,1,0,1,1,0,1}->947,{1,0,0,1,0,1,1,1,0}->951,{1,0,0,1,0,1,1,1,1}->955,{1,0,0,1,1,0,0,0,0}->958,{1,0,0,1,1,0,0,0,1}->962,{1,0,0,1,1,0,0,1,0}->966,{1,0,0,1,1,0,0,1,1}->971,{1,0,0,1,1,0,1,0,0}->975,{1,0,0,1,1,0,1,0,1}->980,{1,0,0,1,1,0,1,1,0}->984,{1,0,0,1,1,0,1,1,1}->988,{1,0,0,1,1,1,0,0,0}->991,{1,0,0,1,1,1,0,0,1}->995,{1,0,0,1,1,1,0,1,0}->999,{1,0,0,1,1,1,0,1,1}->1003,{1,0,0,1,1,1,1,0,0}->1006,{1,0,0,1,1,1,1,0,1}->1010,{1,0,0,1,1,1,1,1,0}->1013,{1,0,0,1,1,1,1,1,1}->1016,{1,0,1,0,0,0,0,0,0}->1018,{1,0,1,0,0,0,0,0,1}->1021,{1,0,1,0,0,0,0,1,0}->1024,{1,0,1,0,0,0,0,1,1}->1028,{1,0,1,0,0,0,1,0,0}->1031,{1,0,1,0,0,0,1,0,1}->1035,{1,0,1,0,0,0,1,1,0}->1039,{1,0,1,0,0,0,1,1,1}->1043,{1,0,1,0,0,1,0,0,0}->1046,{1,0,1,0,0,1,0,0,1}->1050,{1,0,1,0,0,1,0,1,0}->1054,{1,0,1,0,0,1,0,1,1}->1059,{1,0,1,0,0,1,1,0,0}->1063,{1,0,1,0,0,1,1,0,1}->1068,{1,0,1,0,0,1,1,1,0}->1072,{1,0,1,0,0,1,1,1,1}->1076,{1,0,1,0,1,0,0,0,0}->1079,{1,0,1,0,1,0,0,0,1}->1083,{1,0,1,0,1,0,0,1,0}->1087,{1,0,1,0,1,0,0,1,1}->1092,{1,0,1,0,1,0,1,0,0}->1096,{1,0,1,0,1,0,1,0,1}->1101,{1,0,1,0,1,0,1,1,0}->1106,{1,0,1,0,1,0,1,1,1}->1111,{1,0,1,0,1,1,0,0,0}->1115,{1,0,1,0,1,1,0,0,1}->1120,{1,0,1,0,1,1,0,1,0}->1125,{1,0,1,0,1,1,0,1,1}->1130,{1,0,1,0,1,1,1,0,0}->1134,{1,0,1,0,1,1,1,0,1}->1139,{1,0,1,0,1,1,1,1,0}->1143,{1,0,1,0,1,1,1,1,1}->1147,{1,0,1,1,0,0,0,0,0}->1150,{1,0,1,1,0,0,0,0,1}->1154,{1,0,1,1,0,0,0,1,0}->1158,{1,0,1,1,0,0,0,1,1}->1163,{1,0,1,1,0,0,1,0,0}->1167,{1,0,1,1,0,0,1,0,1}->1172,{1,0,1,1,0,0,1,1,0}->1177,{1,0,1,1,0,0,1,1,1}->1182,{1,0,1,1,0,1,0,0,0}->1186,{1,0,1,1,0,1,0,0,1}->1191,{1,0,1,1,0,1,0,1,0}->1196,{1,0,1,1,0,1,0,1,1}->1201,{1,0,1,1,0,1,1,0,0}->1205,{1,0,1,1,0,1,1,0,1}->1210,{1,0,1,1,0,1,1,1,0}->1214,{1,0,1,1,0,1,1,1,1}->1218,{1,0,1,1,1,0,0,0,0}->1221,{1,0,1,1,1,0,0,0,1}->1225,{1,0,1,1,1,0,0,1,0}->1229,{1,0,1,1,1,0,0,1,1}->1234,{1,0,1,1,1,0,1,0,0}->1238,{1,0,1,1,1,0,1,0,1}->1243,{1,0,1,1,1,0,1,1,0}->1247,{1,0,1,1,1,0,1,1,1}->1251,{1,0,1,1,1,1,0,0,0}->1254,{1,0,1,1,1,1,0,0,1}->1258,{1,0,1,1,1,1,0,1,0}->1262,{1,0,1,1,1,1,0,1,1}->1266,{1,0,1,1,1,1,1,0,0}->1269,{1,0,1,1,1,1,1,0,1}->1273,{1,0,1,1,1,1,1,1,0}->1276,{1,0,1,1,1,1,1,1,1}->1279,{1,1,0,0,0,0,0,0,0}->1281,{1,1,0,0,0,0,0,0,1}->1284,{1,1,0,0,0,0,0,1,0}->1287,{1,1,0,0,0,0,0,1,1}->1291,{1,1,0,0,0,0,1,0,0}->1294,{1,1,0,0,0,0,1,0,1}->1298,{1,1,0,0,0,0,1,1,0}->1302,{1,1,0,0,0,0,1,1,1}->1306,{1,1,0,0,0,1,0,0,0}->1309,{1,1,0,0,0,1,0,0,1}->1313,{1,1,0,0,0,1,0,1,0}->1317,{1,1,0,0,0,1,0,1,1}->1322,{1,1,0,0,0,1,1,0,0}->1326,{1,1,0,0,0,1,1,0,1}->1331,{1,1,0,0,0,1,1,1,0}->1335,{1,1,0,0,0,1,1,1,1}->1339,{1,1,0,0,1,0,0,0,0}->1342,{1,1,0,0,1,0,0,0,1}->1346,{1,1,0,0,1,0,0,1,0}->1350,{1,1,0,0,1,0,0,1,1}->1355,{1,1,0,0,1,0,1,0,0}->1359,{1,1,0,0,1,0,1,0,1}->1364,{1,1,0,0,1,0,1,1,0}->1369,{1,1,0,0,1,0,1,1,1}->1374,{1,1,0,0,1,1,0,0,0}->1378,{1,1,0,0,1,1,0,0,1}->1383,{1,1,0,0,1,1,0,1,0}->1388,{1,1,0,0,1,1,0,1,1}->1393,{1,1,0,0,1,1,1,0,0}->1397,{1,1,0,0,1,1,1,0,1}->1402,{1,1,0,0,1,1,1,1,0}->1406,{1,1,0,0,1,1,1,1,1}->1410,{1,1,0,1,0,0,0,0,0}->1413,{1,1,0,1,0,0,0,0,1}->1417,{1,1,0,1,0,0,0,1,0}->1421,{1,1,0,1,0,0,0,1,1}->1426,{1,1,0,1,0,0,1,0,0}->1430,{1,1,0,1,0,0,1,0,1}->1435,{1,1,0,1,0,0,1,1,0}->1440,{1,1,0,1,0,0,1,1,1}->1445,{1,1,0,1,0,1,0,0,0}->1449,{1,1,0,1,0,1,0,0,1}->1454,{1,1,0,1,0,1,0,1,0}->1459,{1,1,0,1,0,1,0,1,1}->1465,{1,1,0,1,0,1,1,0,0}->1470,{1,1,0,1,0,1,1,0,1}->1476,{1,1,0,1,0,1,1,1,0}->1481,{1,1,0,1,0,1,1,1,1}->1486,{1,1,0,1,1,0,0,0,0}->1490,{1,1,0,1,1,0,0,0,1}->1495,{1,1,0,1,1,0,0,1,0}->1500,{1,1,0,1,1,0,0,1,1}->1506,{1,1,0,1,1,0,1,0,0}->1511,{1,1,0,1,1,0,1,0,1}->1517,{1,1,0,1,1,0,1,1,0}->1522,{1,1,0,1,1,0,1,1,1}->1527,{1,1,0,1,1,1,0,0,0}->1531,{1,1,0,1,1,1,0,0,1}->1536,{1,1,0,1,1,1,0,1,0}->1541,{1,1,0,1,1,1,0,1,1}->1546,{1,1,0,1,1,1,1,0,0}->1550,{1,1,0,1,1,1,1,0,1}->1555,{1,1,0,1,1,1,1,1,0}->1559,{1,1,0,1,1,1,1,1,1}->1563,{1,1,1,0,0,0,0,0,0}->1566,{1,1,1,0,0,0,0,0,1}->1570,{1,1,1,0,0,0,0,1,0}->1574,{1,1,1,0,0,0,0,1,1}->1579,{1,1,1,0,0,0,1,0,0}->1583,{1,1,1,0,0,0,1,0,1}->1588,{1,1,1,0,0,0,1,1,0}->1593,{1,1,1,0,0,0,1,1,1}->1598,{1,1,1,0,0,1,0,0,0}->1602,{1,1,1,0,0,1,0,0,1}->1607,{1,1,1,0,0,1,0,1,0}->1612,{1,1,1,0,0,1,0,1,1}->1618,{1,1,1,0,0,1,1,0,0}->1623,{1,1,1,0,0,1,1,0,1}->1629,{1,1,1,0,0,1,1,1,0}->1634,{1,1,1,0,0,1,1,1,1}->1639,{1,1,1,0,1,0,0,0,0}->1643,{1,1,1,0,1,0,0,0,1}->1648,{1,1,1,0,1,0,0,1,0}->1653,{1,1,1,0,1,0,0,1,1}->1659,{1,1,1,0,1,0,1,0,0}->1664,{1,1,1,0,1,0,1,0,1}->1670,{1,1,1,0,1,0,1,1,0}->1675,{1,1,1,0,1,0,1,1,1}->1680,{1,1,1,0,1,1,0,0,0}->1684,{1,1,1,0,1,1,0,0,1}->1689,{1,1,1,0,1,1,0,1,0}->1694,{1,1,1,0,1,1,0,1,1}->1699,{1,1,1,0,1,1,1,0,0}->1703,{1,1,1,0,1,1,1,0,1}->1708,{1,1,1,0,1,1,1,1,0}->1712,{1,1,1,0,1,1,1,1,1}->1716,{1,1,1,1,0,0,0,0,0}->1719,{1,1,1,1,0,0,0,0,1}->1723,{1,1,1,1,0,0,0,1,0}->1727,{1,1,1,1,0,0,0,1,1}->1732,{1,1,1,1,0,0,1,0,0}->1736,{1,1,1,1,0,0,1,0,1}->1741,{1,1,1,1,0,0,1,1,0}->1746,{1,1,1,1,0,0,1,1,1}->1751,{1,1,1,1,0,1,0,0,0}->1755,{1,1,1,1,0,1,0,0,1}->1760,{1,1,1,1,0,1,0,1,0}->1765,{1,1,1,1,0,1,0,1,1}->1770,{1,1,1,1,0,1,1,0,0}->1774,{1,1,1,1,0,1,1,0,1}->1779,{1,1,1,1,0,1,1,1,0}->1783,{1,1,1,1,0,1,1,1,1}->1787,{1,1,1,1,1,0,0,0,0}->1790,{1,1,1,1,1,0,0,0,1}->1794,{1,1,1,1,1,0,0,1,0}->1798,{1,1,1,1,1,0,0,1,1}->1803];
これを全自動スライド bitDP 学習器にぶち込んで係数列を自動生成する．
*/
mint solve(ll n) {
auto s = bitset<57>(n).to_string();
dump(s);
// -------------------- 生成器からの出力を貼る --------------------
vvl coef = { {0, 0, -4, 0, 0, 0, 0, 0, 5, 0, -7, 4, 0, 2, -1}, {0, 0, -4, 0, 0, 0, 0, 0, 4, 0, -6, 5, 0, 0, 0}, {0, 0, -4, 0, 0, 0, 0, 0, 3, 0, -5, 6, 0, -2, 1}, {0, 0, -4, 0, 0, 0, 0, 0, 2, 0, -3, 5, 0, -2, 1}, {0, 0, -4, 0, 0, 0, 0, 0, 1, 0, -2, 6, 0, -4, 2}, {0, 0, -4, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, -4, 2}, {0, 0, -4, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, -2, 1}, {0, 0, -4, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0}, {0, 0, -4, 0, 0, 0, 0, 0, 0, 0, -1, 4, 0, 0, 0}, {0, 0, -4, 0, 0, 0, 0, 0, 0, 0, -1, 3, 0, 2, -1}, {0, 0, -4, 0, 0, 0, 0, 0, 0, 0, -1, 2, 0, 4, -2}, {0, 0, -4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, -2}, {0, 0, -4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, -1}, {0, 0, -4, 0, 0, 0, 0, 0, 0, 0, 1, -2, 0, 5, -1}, {0, 0, -4, 0, 0, 0, 0, 0, 0, 0, 1, -2, 0, 4, 0}, {0, 0, -4, 0, 0, 0, 0, 0, 0, 0, 1, -2, 0, 3, 1} };
vl dp = { -1, 0, 1, 0, 1, 2, 4, 0, 1, 2, 4, 5, 7, 9, 11 };
// --------------------------------------------------------------
// ここ以降は書き換える必要はない．
int B = msb(sz(coef)) - 1;
repe(si, s) {
vl ndp;
ndp.reserve(sz(dp));
int offset = 1;
rep(b, B) {
int d = si - '0';
int w = 1 << b;
ndp.insert(ndp.end(), dp.begin() + (offset + d * w), dp.begin() + (offset + (d + 1) * w));
offset += 2 * w;
}
int k0 = (si - '0') << B;
int k1 = k0 + (1 << B) - 1;
repi(k, k0, k1) {
ll tmp = 0;
rep(t, sz(dp)) tmp += dp[t] * coef[k][t];
ndp.push_back(tmp);
}
dp = move(ndp);
}
return dp[0];
}
int main() {
// input_from_file("input.txt");
// output_to_file("output.txt");
// zikken();
//【方法】
// 愚直を書いて集めた学習データをもとにスライド bitDP のコードを自動生成する．
int T;
cin >> T;
rep(hoge, T) {
ll n;
cin >> n;
cout << solve(n) << "\n";
}
}