#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <string.h>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <math.h>
#include <algorithm>
#include <numeric>
#include <random>

//#include <atcoder/convolution>
//#include <atcoder/math>
//#include <atcoder/maxflow>
//#include <atcoder/mincostflow>
//#include <atcoder/modint>
//#include <atcoder/scc>
//#include <atcoder/string>
//#include <atcoder/twosat>
//using namespace atcoder;

using namespace std;


// マクロ&定数&関数 ================================================
typedef int Int;
typedef int INt;
typedef unsigned int uint;
typedef long long ll;
typedef long double ld;

typedef pair<ll, ll> pll;
typedef pair<int, int> pint;

typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<bool> vbool;
typedef vector<string> vstring;

typedef vector<pair<int, int>> vpint;
typedef vector<pair<ll, ll>> vpll;
typedef vector<pair<double, double>> vpdouble;

typedef vector<vector<int>> vvint;
typedef vector<vector<ll>> vvll;
typedef vector<vpint> vvpint;
typedef vector<vpll> vvpll;
typedef vector<vector<double>> vvdouble;
typedef vector<vector<string>> vvstring;
typedef vector<vector<bool>> vvbool;

typedef vector<vector<vector<ll>>> vvvll;
typedef vector<vector<vector<pll>>> vvvpll;
typedef vector<vector<vector<bool>>> vvvbool;
typedef vector<vector<vector<double>>> vvvdouble;
typedef vector<vector<vector<vector<double>>>> vvvvdouble;

const ll LLINF = 1e18 + 1;
const int DX[9] = { 0,  0, 1, -1, 1,  1, -1, -1, 0 }; // 4;４近傍
const int DY[9] = { 1, -1, 0,  0, 1, -1,  1, -1, 0 }; // 8:８近傍 9:(0,0)を含む
const double PI = 3.14159265358979323846264338327950288;
const double EPS = 1e-7;

//VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV

const ll MOD = 1000000007; //10^9 + 7

//VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV


template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } else return false; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } else return false; }


//---------------------------------------------------------------
//  オーバーフローチェック
//---------------------------------------------------------------
bool is_overflow(ll a, ll b) {
    ll M = numeric_limits<ll>::max();
    return (a >= M / b);
}

//---------------------------------------------------------------
//  整数の乱数生成
//---------------------------------------------------------------
ll random_int(ll start, ll last) { return start + rand() % (last - start + 1); }

//---------------------------------------------------------------
//  2次元配列の表示(デバッグ用)
//---------------------------------------------------------------
template<class T>
void print2D(vector<vector<T>> A)
{
    for (vector<T> aa : A) {
        for (T a : aa)
            cout << a << " ";
        cout << endl;
    }
    cout << endl;
}

//---------------------------------------------------------------
//  x∈[a, b)
//---------------------------------------------------------------
bool is_in(ll x, ll a, ll b) { return (a <= x && x < b); }

//---------------------------------------------------------------
//  文字系 → 整数
//---------------------------------------------------------------
ll to_int(string S) { return stoll(S); }
ll to_int(char c) { return int(c) - int('0'); }
ll to_int(const char *c) { return atoi(c); }

//---------------------------------------------------------------
//  2次元累積和 (ゼロパディング有り)
//---------------------------------------------------------------
template<class T>
vector<vector<T>> get_accum(vector<vector<T>> A)
{
    T H = A.size();
    T W = A[0].size();

    vector<vector<T>> accum(H + 1, vector<T>(W + 1, 0));
    for (int h = 0; h < H; h++)
        for (int w = 0; w < W; w++)
            accum[h + 1][w + 1] = A[h][w];

    for (int h = 0; h <= H; h++)
        for (int w = 0; w < W; w++)
            accum[h][w + 1] += accum[h][w];

    for (int h = 0; h < H; h++)
        for (int w = 0; w <= W; w++)
            accum[h + 1][w] += accum[h][w];

    return accum;
}

//---------------------------------------------------------------
//  約数列挙 O(√N)
//---------------------------------------------------------------
vll divisor(ll n) {
    vll ret;
    for (ll i = 1; i * i <= n; i++) { if (n % i == 0) { ret.push_back(i);	if (i * i != n) ret.push_back(n / i); } }
    sort(begin(ret), end(ret));	return (ret);
}

//---------------------------------------------------------------
// N未満のすべての素数判定(エラトステネスの篩)
//---------------------------------------------------------------
vbool searchSosuu(ll N) {
    vbool sosuu;
    for (ll i = 0; i < N; i++) { sosuu.emplace_back(true); }
    sosuu[0] = false;	sosuu[1] = false;
    for (ll i = 2; i < N; i++) { if (sosuu[i]) { for (ll j = 2; i * j < N; j++) { sosuu[i * j] = false; } } }
    return sosuu;
}

//---------------------------------------------------------------
// 素因数分解　O(√N)
//---------------------------------------------------------------
vpll to_prime(ll n) {
    vpll prime_factor;
    for (ll i = 2; i * i <= n; i++) {
        ll count = 0; while (n % i == 0) { count++; n /= i; }
        if (count) { pair<ll, ll> temp = { i, count };	prime_factor.emplace_back(temp); }
    }
    if (n != 1) { pair<ll, ll> temp = { n, 1 }; prime_factor.emplace_back(temp); }
    return prime_factor;
}

//---------------------------------------------------------------
// 高速素因数分解(前処理O(N), 分解O(logN))
//---------------------------------------------------------------
class FastPrime
{
public:
    vll div;    // i の約数のうちの1つ。
    vbool is_sosuu; // i が素数であるか。

    FastPrime(ll N) : div(N + 10, -1), is_sosuu(N + 10, true)
    {
        for (ll i = 2; i < N; i++)
            if (div[i] == -1)
                for (ll j = 2; i * j <= N; j++)
                {
                    div[i * j] = i;
                    is_sosuu[i * j] = false;
                }
    }

    vpll to_prime(ll N)
    {
        if (N == 1) return vpll({});

        vll divs;
        while (div[N] != -1)
        {
            divs.emplace_back(div[N]);
            N /= div[N];
        }
        if (N > 1) divs.emplace_back(N);

        sort(divs.begin(), divs.end());

        vpll primes;
        ll count = 1;
        for (int i = 1; i < divs.size(); i++)
        {
            if (divs[i] > divs[i - 1])
            {
                primes.emplace_back(pll(divs[i - 1], count));
                count = 0;
            }
            count++;
        }
        primes.emplace_back(pll(divs[divs.size() - 1], count));

        return primes;
    }

};

//---------------------------------------------------------------
// 最大公約数（ユークリッドの互除法）
//---------------------------------------------------------------
ll gcd(ll a, ll b) {
    if (a < b) { ll tmp = a;	a = b; b = tmp; }
    ll r = a % b;
    while (r != 0) { a = b; b = r; r = a % b; }
    return b;
}

//---------------------------------------------------------------
// 約分
//---------------------------------------------------------------
pll reduce(ll a, ll b) {
    ll g = gcd(a, b);
    return pll(a / g, b / g);
}

//---------------------------------------------------------------
// 最小公倍数
//---------------------------------------------------------------
ll lcm(ll a, ll b) { ll temp = gcd(a, b); return temp * (a / temp) * (b / temp); }

//---------------------------------------------------------------
// 階乗
//---------------------------------------------------------------
ll factorial(ll n, ll mod = MOD) { if (n <= 1) { return 1; }return (n * (factorial(n - 1))) % mod; }

//---------------------------------------------------------------
// 高速コンビネーション計算(前処理:O(N) 計算:O(1))
//---------------------------------------------------------------
// テーブルを作る前処理
ll comb_const = 3000005;
vll fac(comb_const), finv(comb_const), inv(comb_const);
bool COMineted = false;
void COMinit(ll mod = MOD) {
    fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1;
    for (ll i = 2; i < comb_const; i++) {
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
    COMineted = true;
}
// 二項係数計算
ll COM(ll n, ll k, ll mod = MOD) {
    if (COMineted == false) COMinit(mod);
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return (fac[n] * (finv[k] * finv[n - k] % mod)) % mod;
}

//---------------------------------------------------------------
// 繰り返し２乗法 base^sisuu
//---------------------------------------------------------------
ll RepeatSquaring(ll base, ll sisuu, ll mod = MOD) {
    if (sisuu < 0) { cout << "RepeatSquaring: 指数が負です!" << endl; return 0; }
    if (sisuu == 0) return 1;
    if (sisuu % 2 == 0) { ll t = RepeatSquaring(base, sisuu / 2, mod) % mod;	return (t * t) % mod; }
    return (base * RepeatSquaring(base, sisuu - 1, mod)) % mod;
}

//---------------------------------------------------------------
// 高速単発コンビネーション計算(O(logN))
//---------------------------------------------------------------
ll fast_com(ll a, ll b, ll mod = MOD) {
    ll bunshi = 1;	ll bunbo = 1;
    for (ll i = 1; i <= b; i++) { bunbo *= i;	bunbo %= mod; bunshi *= (a - i + 1); bunshi %= mod; }
    ll ret = bunshi * RepeatSquaring(bunbo, mod - 2, mod); ret %= mod;
    while (ret < 0) { ret += mod; }
    return ret;
}

//---------------------------------------------------------------
// 整数をビットのリストに変換する ll->vbool
//---------------------------------------------------------------
vbool to_bitlist(ll bit, ll fixed_size = 1) {
    if (bit == 0) return vbool(fixed_size, 0);
    vbool list;
    while (bit > 0) { list.emplace_back(bit & 1);	bit /= 2; }
    while (list.size() < fixed_size) { list.emplace_back(0); }
    return list;
}

//---------------------------------------------------------------
// 立っているビットの数をカウントする
//---------------------------------------------------------------
ll bit_count(ll bit) {
    ll ret = 0;
    while (bit) {
        ret += bit % 2;
        bit /= 2;
    }
    return ret;
}

//---------------------------------------------------------------
// XORの階乗 0^1^...^N (O(1))
//---------------------------------------------------------------
ll xor_fac(ll N)
{
    if (N == 0) return 0;

    ll n_pair = (N - 1) / 2;
    ll n_one = n_pair + 1;

    if (n_pair * 2 + 1 == N) {
        return n_one % 2;
    }
    else {
        return (n_one % 2) ^ N;
    }
}

//---------------------------------------------------------------
// 座標圧縮(O(NlogN))   0スタートになることに注意！
//---------------------------------------------------------------
class PosPress
{
public:
    vll pressed;
    map<ll, ll> func; // 圧縮後を知りたい
    map<ll, ll> rev;  // 圧縮前を知りたい

    PosPress(vll P) {
        pressed = P; sort(P.begin(), P.end()); func[P[0]] = 0;	rev[0] = P[0]; ll next = 1;
        for (int i = 1; i < P.size(); i++) { if (P[i] != P[i - 1]) { func[P[i]] = next; rev[next] = P[i]; next++; } }
        for (int i = 0; i < P.size(); i++) { pressed[i] = func[pressed[i]]; }
    }
};

//---------------------------------------------------------------
// 行列積(O(N^3))
//---------------------------------------------------------------
vvll mat_cross(vvll A, vvll B) {
    ll N = A.size(); ll K = B.size(); ll M = B[0].size();
    vvll C(N, vll(M));

    // 行列積の計算(+, * は |, & でもOK) 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            for (int k = 0; k < K; k++)
                C[i][j] += A[i][k] * B[k][j];
    return C;
}

//---------------------------------------------------------------
// 2直線の交差判定(直線(x1, y1)->(x2, y2) と 直線(X1, Y1)->(X2, Y2))
//---------------------------------------------------------------
bool is_cross(ll x1, ll y1, ll x2, ll y2, ll X1, ll Y1, ll X2, ll Y2) {
    ll dx_ai = X1 - x1;	ll dy_ai = Y1 - y1;
    ll dx_bi = X1 - x2;	ll dy_bi = Y1 - y2;
    ll dx_ai2 = X2 - x1; ll dy_ai2 = Y2 - y1;
    ll dx_bi2 = X2 - x2; ll dy_bi2 = Y2 - y2;
    ll si = dx_ai * dy_bi - dy_ai * dx_bi;
    ll si2 = dx_ai2 * dy_bi2 - dy_ai2 * dx_bi2;
    ll si3 = dx_ai * dy_ai2 - dy_ai * dx_ai2;
    ll si4 = dx_bi * dy_bi2 - dy_bi * dx_bi2;
    return (si * si2 < 0 && si3 * si4 < 0);
}

//---------------------------------------------------------------
// 最長増加部分列の長さ(O(NlogN))
//---------------------------------------------------------------
ll LSI(vll vec)
{
    ll size = vec.size();
    vll lsi(size + 1, LLINF); // 長さjを作った時の右端の最小値
    lsi[0] = 0;	lsi[1] = vec[0];
    for (ll i = 1; i < size; i++)
    {
        // 初めてvec[i]の方が小さくなるところを探す
        auto Iter = lower_bound(lsi.begin(), lsi.end(), vec[i]);
        ll idx = Iter - lsi.begin();
        if (idx > 0 && lsi[idx - 1] < vec[i]) { lsi[idx] = vec[i]; }
    }
    for (ll i = size; i >= 0; i--) { if (lsi[i] < LLINF) { return i; } }
}

//---------------------------------------------------------------
// LCS(最長共通部分列) O(|S||T|)
//---------------------------------------------------------------
string LCS(string S, string T)
{
    vvll dp(S.length() + 1);
    for (int i = 0; i < dp.size(); i++) { vll t(T.length() + 1, 0); dp[i] = t; }

    for (int i = 0; i < S.length(); i++) {
        for (int j = 0; j < T.length(); j++) {
            dp[i + 1][j + 1] = max({ dp[i][j] + ll(S[i] == T[j]), dp[i + 1][j], dp[i][j + 1], dp[i + 1][j + 1] });
        }
    }
    ll len = dp[S.length()][T.length()];
    string ans = "";
    ll i = dp.size() - 1;
    ll j = dp[0].size() - 1;
    while (len > 0) {
        if (dp[i - 1][j] == len) { i--; }
        else if (dp[i][j - 1] == len) { j--; }
        else { ans += S[i - 1]; i--; j--; len--; }
    }

    reverse(ans.begin(), ans.end());
    return ans;
}
vll LCS(vll S, vll T)
{
    vvll dp(S.size() + 1);
    for (int i = 0; i < dp.size(); i++) { vll t(T.size() + 1, 0); dp[i] = t; }

    for (int i = 0; i < S.size(); i++) {
        for (int j = 0; j < T.size(); j++) {
            dp[i + 1][j + 1] = max({ dp[i][j] + ll(S[i] == T[j]), dp[i + 1][j], dp[i][j + 1], dp[i + 1][j + 1] });
        }
    }
    ll len = dp[S.size()][T.size()];
    vll ans;
    ll i = dp.size() - 1;
    ll j = dp[0].size() - 1;
    while (len > 0) {
        if (dp[i - 1][j] == len) { i--; }
        else if (dp[i][j - 1] == len) { j--; }
        else { ans.emplace_back(S[i - 1]); i--; j--; len--; }
    }

    reverse(ans.begin(), ans.end());
    return ans;
}

//---------------------------------------------------------------
// 木の根からの深さ
//---------------------------------------------------------------
vll tree_depth(vvll edge, ll root)
{
    ll n_node = edge.size();
    vll dist(n_node, LLINF);
    dist[root] = 0;

    stack<pll> S;
    S.push({ root, 0 });

    while (!S.empty())
    {
        ll node = S.top().first;
        ll d = S.top().second;
        dist[node] = d;

        S.pop();

        for (int i = 0; i < edge[node].size(); i++) {
            if (dist[edge[node][i]] == LLINF) {
                S.push({ edge[node][i], d + 1 });
            }
        }
    }

    return dist;
}

//---------------------------------------------------------------
// ワーシャルフロイド法(O(N^3)) d: 正方行列(N*N)
//---------------------------------------------------------------
vvll warshall_floyd(vvll d) {
    ll n = d.size();
    for (int k = 0; k < n; k++) {       // 経由する頂点
        for (int i = 0; i < n; i++) {    // 始点
            for (int j = 0; j < n; j++) {  // 終点
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    return d;
}

//---------------------------------------------------------------
// Union Find
//---------------------------------------------------------------
class UnionFind {
private:
    vll siz; // 素集合のサイズを表す配列(1 で初期化)

public:
    ll n_group; // 集合の数
    vll par; // 各元の親を表す配列

    // Constructor
    UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
        n_group = sz_;
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);  // resize だとなぜか初期化されなかった
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }

    // Member Function
    // Find
    ll root(ll x) { // 根の検索
        while (par[x] != x) {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }

    // Union(Unite, Merge)
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        n_group--;
        return true;
    }

    // 連結判定
    bool issame(ll x, ll y) {
        return root(x) == root(y);
    }

    // x を含むグループの大きさ
    ll size(ll x) {
        return siz[root(x)];
    }
};

//---------------------------------------------------------------
// ダイクストラ(O(ElogV))   edge: 隣接リスト from->pair{to, cost}
//---------------------------------------------------------------
class Dijkstra
{
private:
    vll past; // (iまで最短で行くときの一つ前)

public:
    vll dist; // iまでの最短距離

    // edge[i] -> {to, cost}
    Dijkstra(vvpll edge, ll start) : dist(edge.size(), LLINF), past(edge.size(), -1)
    {
        using Pi = pll;
        priority_queue< Pi, vector< Pi >, greater< Pi > > que;
        dist[start] = 0;
        que.emplace(dist[start], start);
        while (!que.empty()) {
            ll cost;
            int idx;
            tie(cost, idx) = que.top();
            que.pop();
            if (dist[idx] < cost) continue;
            for (int i = 0; i < edge[idx].size(); i++)
            {
                ll next_cost = cost + edge[idx][i].second;
                if (dist[edge[idx][i].first] <= next_cost) continue;
                dist[edge[idx][i].first] = next_cost;
                past[edge[idx][i].first] = idx;
                que.emplace(dist[edge[idx][i].first], edge[idx][i].first);
            }
        }
    }

    // goalまでの最短経路
    vll shortest(ll goal)
    {
        vll ret;
        while (goal != -1)
        {
            ret.emplace_back(goal);
            goal = past[goal];
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

//---------------------------------------------------------------
// LCA: 最近共通祖先 (O())
//---------------------------------------------------------------
class Lca
{
private:
    vvll doubling;
    ll n_bit = 30;

public:

    vll depth; // 根0からiまでの最短距離

    // edge[i] -> {to, cost}
    Lca(vvll edge, ll root = 0) : doubling(50, vll(edge.size(), -1))
    {
        // 深さ
        depth = tree_depth(edge, root);

        // ダブリングで親を辿れるようにする
        // jから2^i回親を辿ったノード
        doubling[0][0] = -1;
        for (int i = 1; i < edge.size(); i++)
            for (int j : edge[i])
                if (depth[i] > depth[j]) { doubling[0][i] = j; break; }
        for (int i = 1; i < n_bit; i++)
            for (int j = 0; j < edge.size(); j++) {
                if (doubling[i - 1][j] != -1) doubling[i][j] = doubling[i - 1][doubling[i - 1][j]];
                else doubling[i][j] = -1;
            }
    }

    // aとbの最近共通祖先
    ll get_lca(ll a, ll b)
    {
        // depth[a] >= depth[b]にする
        if (depth[a] < depth[b]) swap(a, b);
        ll oa = a;
        ll ob = b;
        ll d = depth[a] - depth[b];

        // aをdだけさかのぼる。
        vbool bit = to_bitlist(d, n_bit);
        for (int i = 0; i < n_bit; i++)if (bit[i]) a = doubling[i][a];

        // depth[a] == depth[b]になっている。
        for (int i = n_bit - 1; i >= 0; i--) {
            if (doubling[i][a] == doubling[i][b]) continue;
            a = doubling[i][a];	b = doubling[i][b];
        }
        return a == b ? a : doubling[0][a];
    }

    // パスの長さ
    ll path_len(ll a, ll b)
    {
        return depth[a] + depth[b] - 2 * depth[get_lca(a, b)];
    }

    // パスに含まれる頂点集合
    vll nodes_on_path(ll a, ll b)
    {
        if (a == b) return vll({ a });

        vll ret;
        ll lca = get_lca(a, b);
        while (a != lca) {
            ret.emplace_back(a);
            a = doubling[0][a];
        }
        while (b != lca) {
            ret.emplace_back(b);
            b = doubling[0][b];
        }
        ret.emplace_back(lca);

        return ret;
    }

};

//---------------------------------------------------------------
// Z-algorithm(SとS[i:]の最長接頭辞長)  O(|S|)
//---------------------------------------------------------------
vll Zalgorithm(string S)
{
    ll n = S.size();
    vll Z(n, 0);
    ll start = -1;
    ll last = -1;
    for (ll i = 1; i < n; i++) {
        if (start >= 0) { Z[i] = min(Z[i - start], last - i); chmax(Z[i], 0LL); }
        while (i + Z[i] < S.size() && S[Z[i]] == S[i + Z[i]])
            Z[i] ++;
        if (last < i + Z[i]) { last = i + Z[i]; start = i; }
    }
    Z[0] = n;
    return Z;
}
vll Zalgorithm(vll S)
{
    ll n = S.size();
    vll Z(n, 0);
    ll start = -1;
    ll last = -1;
    for (ll i = 1; i < n; i++) {
        if (start >= 0) { Z[i] = min(Z[i - start], last - i); chmax(Z[i], 0LL); }
        while (i + Z[i] < S.size() && S[Z[i]] == S[i + Z[i]])
            Z[i] ++;
        if (last < i + Z[i]) { last = i + Z[i]; start = i; }
    }
    Z[0] = n;
    return Z;
}

//---------------------------------------------------------------
// 二部グラフ判定(O(E))  edge -> リスト
//---------------------------------------------------------------
class Bipartite
{
private:
    ll N;
public:
    vll color;   // 2色に塗り分けた時の塗り分け方
    bool is_bipartite; // 2部グラフであるか
    Bipartite(vvll edge) : color(edge.size(), -1)
    {
        N = edge.size();
        color[0] = 0;

        queue<ll> Q;
        Q.push(0);
        while (!Q.empty())
        {
            ll now = Q.front();
            Q.pop();

            for (int i : edge[now])
            {
                if (color[i] == -1)
                {
                    color[i] = (color[now] == 0 ? 1 : 0);
                    Q.push(i);
                }
                else if (color[i] == color[now])
                {
                    is_bipartite = false;
                    return;
                }
            }
        }
        is_bipartite = true;
    }
};

//---------------------------------------------------------------
// ダブリング  (行先のリスト, コスト) ← コストは任意
//---------------------------------------------------------------
class Doubling
{
private:
    ll M = 100;
    vvll doubling;
    vvll cost;
    bool have_cost = false;

public:
    // to[i]: i から1回移動した先
    // fee[i]: i から to[i]へと移動するコスト(任意)
    Doubling(vll to, vll fee = {}) : doubling(M, vll(to.size(), -1)), cost(M, vll(to.size(), 0))
    {
        ll N = to.size();
        have_cost = fee.size() > 0;
        for (int i = 0; i < N; i++)
        {
            doubling[0][i] = to[i];
            if (have_cost)
                cost[0][i] = fee[i];
        }
        for (int i = 1; i < M; i++)
        {
            for (int j = 0; j < N; j++)
            {
                doubling[i][j] = doubling[i - 1][doubling[i - 1][j]];
                if (have_cost)
                    cost[i][j] = cost[i - 1][j] + cost[i - 1][doubling[i - 1][j]];
            }
        }
    }

    // from から K 回移動した先
    ll destination(ll from, ll K)
    {
        vbool bits = to_bitlist(K);
        ll now = from;
        ll sum = 0;
        for (int i = 0; i < bits.size(); i++)
        {
            if (bits[i])
            {
                now = doubling[i][now];
            }
        }
        return now;
    }

    // from から K 回移動するコストの合計
    ll get_cost(ll from, ll K)
    {
        vbool bits = to_bitlist(K);
        ll now = from;
        ll sum = 0;
        for (int i = 0; i < bits.size(); i++)
        {
            if (bits[i])
            {
                sum += cost[i][now];
                now = doubling[i][now];
            }
        }
        return sum;
    }

};

//---------------------------------------------------------------
// ベルマンフォード(O(EV))  edge, from, to -> (cost, have_neg_roop)
//---------------------------------------------------------------
pair<ll, bool> BelmanFord(vvpll edge, ll from, ll to)
{

    ll N = edge.size(); //頂点の数
    vll d(N, LLINF); //始点から添え字の頂点に行くのにかかるコスト
    d[from] = 0; //始点を0にする

    bool have_negroop = false;

    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j < N; j++) {

            for (int k = 0; k < edge[j].size(); k++)
            {
                ll from = j;
                ll to = edge[j][k].first;
                ll cost = edge[j][k].second;

                if (d[to] > d[from] + cost) {  //移動した後のコストが小さいと、頂点のコストを更新
                    d[to] = d[from] + cost;

                    //頂点の数と同じ回数ループすると、負の閉路があるのでループをぬける
                    if (i == N - 1)
                    {
                        have_negroop = true;
                        break;
                    }
                }
            }
        }
    }

    return pll(d[to], have_negroop);
}

//---------------------------------------------------------------
// 遅延セグ木(構築O(N), 更新・取得(logN))
//---------------------------------------------------------------
/*
<コンストラクタ>
    lazy_segtree<S, op, e, ll, mapping, composition, id> seg(A);


<構築> (pos に x を代入)
    seg.set(int pos, ll x);

<単一取得>
    seg.get(int pos);

<区間取得> ([l, r)を取得)
    seg.prod(int l, int r);

<全区間取得>
    seg.all_prod();

<更新>
    seg.apply(int pos, ll x);
    seg.apply(int l, int r, ll x);

<二分探索> (g(op(a[l], a[l + 1], ..., a[r - 1])) = true となる最大の r)
    seg.max_right<g>(int l);

<二分探索> (g(op(a[l], a[l + 1], ..., a[r - 1])) = true となる最小の l)
    seg.min_left<g>(int r);

*/
template <class S, S(*op)(S, S), S(*e)(), class F, S(*mapping)(F, S), F(*composition)(F, F), F(*id)()>
struct lazy_segtree {
private:
    int ceil_pow2(int n) {
        int x = 0;
        while ((1U << x) < (unsigned int)(n)) x++;
        return x;
    }
public:
    lazy_segtree() : lazy_segtree(0) {}
    lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    lazy_segtree(const std::vector<S> &v) : _n(int(v.size())) {
        log = ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return e();

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push(r >> i);
        }

        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    template <bool (*g)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*g)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return g(x); });
    }
    template <class G> int min_left(int r, G g) {
        assert(0 <= r && r <= _n);
        assert(g(e()));
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(op(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

private:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }
};

// モノイドの型
//struct S {
//    ll value; // 値
//    int size;  // 区間の大きさ
//};
//
//// 写像の定義(data部分に用いる関数, 区間の合成)
//S op(S l, S r) { return S{ max(l.value, r.value), l.size + r.size }; }
//
//// 単位元
//S e() { return S{ 0, 0 }; }
//
//// F(x) (遅延評価するときの関数・加算or代入, lazyのretへの当て方)
//S mapping(ll f, S x) { return S{ max(x.value, f), x.size }; }
//
//// 作用素(lazy同士)の合成
//ll composition(ll l, ll r) { return max(l, r); }
//
//// lazyの単位元
//ll id() { return 0; }
//
//// 二分探索の関数
//ll V;
//bool g(S v) {
//    return V > v.value;
//}




int main() {

    //////==================================
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(25);
    //////==================================


    /*
    　　　～思いついたことはとりあえず絶対メモする！！～


    　　　　　～オーバーフローに注意！！！～
    */



    ll N;
    cin >> N;

    vll grundy(N + 10, 0);

    for (int i = 1; i <= N; i++)
    {
        vbool used(N + 10, false);

        used[grundy[i / 2] ^ grundy[i - (i / 2)]] = true;
        
        if(i % 3 == 0)
            used[grundy[i / 3]] = true;
        if (i % 3 == 1)
            used[grundy[i / 3 + 1]] = true;
        if (i % 3 == 2)
            used[grundy[i / 3]] = true;


        for (int j = 0; j < N + 10; j++)
        {
            if (!used[j])
            {
                grundy[i] = j;
                break;
            }
        }

    }

    cout << (grundy[N] != 0 ? "A" : "B") << endl;







}