using namespace std;
using ii = pair<int, int>;
using vii = vector<ii>;
int const NMAX = 100 + 11;
int n, m, row_cnt[NMAX], r0, c0;
bool visited[NMAX][NMAX];
vii ans;
void solve(void)
{
    int c;
    c = c0;
    if (r0 == 0)
    {
        ans.pop_back();
        row_cnt[r0]++;
    }
    for (int r = 0; r < n; ++r)
    {
        visited[r][c] = true;
        row_cnt[r]--;
        ans.emplace_back(r, c);
        while (row_cnt[r] > 0)
        {
            auto it = find(visited[r], visited[r] + m, false);
            *it = true;
            ans.emplace_back(r, distance(visited[r], it));
            row_cnt[r]--;
        }
        c = ans.back().second;
        if (r + 1 == r0 and c == c0)
        {
            int sz = ans.size();
            swap(ans[sz - 1], ans[sz - 2]);
            c = ans.back().second;
        }
    }
}
int main(void)
{
    cin >> n >> m;
    cin >> r0 >> c0;
    r0--, c0--;
    fill(row_cnt, row_cnt + n, m);
    row_cnt[r0]--;
    visited[r0][c0] = true;
    ans.push_back({r0, c0});
    solve();
    for (auto [r, c] : ans)
        cout << r + 1 << " " << c + 1 << endl;
    cout << endl;
    return 0;
}

using namespace std;
using ii = pair<int, int>;
using vi = vector<int>;
int const NMAX = 1e5 + 11;
int n, a[NMAX], freq[NMAX];
set<ii, greater<ii>> ordered_freq;
int main(void)
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        memset(freq, 0, sizeof(freq));
        ordered_freq.clear();
        for (int i = 0; i < n; ++i)
            cin >> a[i], freq[a[i]]++;
        for (int i = 0; i < NMAX; ++i)
            if (freq[i] > 0)
                ordered_freq.emplace(freq[i], i);
        auto [ftop, xtop] = *ordered_freq.begin();
        int cnt = 0, acc = 0;
        for (auto [fi, i] : ordered_freq)
        {
            if (fi < ftop)
                break;
            ++cnt;
            acc += ftop;
        }
        cout << (n - acc) / (ftop - 1) + cnt - 1 << endl;
    }
    return 0;
}

using namespace std;
using ii = pair<int, int>;
using vi = vector<int>;
int const NMAX = 1e5 + 11;
int n, freq[NMAX];
vi a;
set<ii, greater<ii>> s;
void build(void)
{
    s.emplace(0, 0), s.emplace(0, -1), s.emplace(0, -2);
    for (int i = 1; i < NMAX; ++i)
        s.emplace(freq[i] / 2, i);
}
void update(char type, int x)
{
    s.erase({freq[x] / 2, x});
    if (type == '+')
        freq[x]++;
    else
        freq[x]--;
    s.emplace(freq[x] / 2, x);
}
bool query(void)
{
    auto [m0, x0] = *s.begin();
    auto [m1, x1] = *next(s.begin());
    auto [m2, x2] = *next(next(s.begin()));
    if (m0 < 2)
        return false;
    m0 -= 2;
    if (m0 + m1 + m2 < 2)
        return false;
    return true;
}
int main(void)
{
    int q, x;
    char type;
    cin >> n;
    a.resize(n);
    for (auto &ai : a)
        cin >> ai, freq[ai]++;
    build();
    cin >> q;
    while (q--)
    {
        cin >> type >> x;
        update(type, x);
        cout << (query() ? "YES" : "NO") << endl;
    }
    return 0;
}

using namespace std;
int main(void)
{
    int t, n;
    cin >> t;
    while (t--)
    {
        cin >> n;
        cout << n / 2 + 1 << endl;
    }
    return 0;
}

using namespace std;
int solve(int n, string s)
{
    int start = 0;
    if (s[start] == s[(start - 1 + n) % n])
    {
        do
        {
            start = (start - 1 + n) % n;
        } while (start != 0 and s[start] == s[(start - 1 + n) % n]);
        if (start == 0)
            return (n + 3 - 1) / 3;
    }
    int cnt = 0, ans = 0;
    char c = s[start];
    for (int i = 0; i <= n; ++i)
    {
        if (s[(start + i) % n] == c)
        {
            cnt++;
        }
        else
        {
            ans += cnt / 3;
            cnt = 1;
            c = s[(start + i) % n];
        }
    }
    return ans;
}
int main(void)
{
    int t, n;
    string s;
    cin >> t;
    while (t--)
    {
        cin >> n;
        cin >> s;
        cout << solve(n, s) << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
int const NMAX = 2e5 + 11;
ll n, a[NMAX];
ll solve(void)
{
    int i = n - 1;
    ll ans = 0;
    while (i > 0)
    {
        int j = i;
        while (j > 0 and a[j] >= a[j - 1])
            --j;
        if (j > 0)
        {
            ans += (a[j - 1] - a[j]);
            a[j] = a[j - 1];
        }
        i = j;
    }
    return ans;
}
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        cout << solve() << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using vi = vector<int>;
int const NMAX = 2e5 + 11;
int n, a[NMAX];
ll k;
bool cyclic(void)
{
    bool zero = false;
    for (int i = 0; i < n; ++i)
    {
        if (a[i] < 0)
            return false;
        if (a[i] == 0)
            zero = true;
    }
    if (zero)
        return true;
    else
        return false;
}
void op(void)
{
    int d = *max_element(a, a + n);
    for (int i = 0; i < n; ++i)
        a[i] = d - a[i];
}
int main(void)
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n >> k;
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        ll ki = 0;
        while (ki != k and not cyclic())
        {
            op();
            ++ki;
        }
        if ((k - ki) % 2 == 1)
            op();
        for (int i = 0; i < n; ++i)
            cout << a[i] << " ";
        cout << endl;
    }
    return 0;
}

using namespace std;
int main(void)
{
    int t, n, ai;
    cin >> t;
    while (t--)
    {
        cin >> n;
        set<int> s;
        for (int i = 0; i < n; ++i)
        {
            cin >> ai;
            s.insert(ai);
        }
        if (s.size() == 1)
            cout << n << endl;
        else
            cout << 1 << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
int const MOD = 1e9 + 7;
int const NMAX = 1e6 + 11;
ll fact[NMAX], inv[NMAX];
void precompute()
{
    fact[0] = 1;
    for (int i = 1; i < NMAX; i++)
        fact[i] = fact[i - 1] * i % MOD;
    inv[1] = 1;
    for (int i = 2; i < NMAX; ++i)
        inv[i] = (MOD - (MOD / i) * inv[MOD % i] % MOD) % MOD;
}
int extended_gcd(int a, int b, int &x, int &y)
{
    x = 1, y = 0;
    int x1 = 0, y1 = 1, a1 = a, b1 = b;
    while (b1)
    {
        int q = a1 / b1;
        tie(x, x1) = make_tuple(x1, x - q * x1);
        tie(y, y1) = make_tuple(y1, y - q * y1);
        tie(a1, b1) = make_tuple(b1, a1 - q * b1);
    }
    return a1;
}
ll inverse(int a)
{
    if (a < NMAX)
        return inv[a];
    int x, y;
    int mod = MOD;
    int g = extended_gcd(a, mod, x, y);
    if (g != 1)
    {
        return 0;
    }
    else
    {
        x = (x % MOD + MOD) % MOD;
        return x;
    }
}
ll nck(int n, int k)
{
    return fact[n] * inverse(fact[k]) % MOD * inverse(fact[n - k]) % MOD;
}
ll mult(ll a, ll b) { return ((a % MOD) * (b % MOD)) % MOD; }
ll sub(ll a, ll b) { return ((a % MOD) - (b % MOD) + MOD) % MOD; }
int main(void)
{
    int n;
    cin >> n;
    precompute();
    ll ans = fact[n];
    ll cur = 1;
    for (int k = 0; k < n - 1; ++k)
    {
        cur = mult(2, cur);
    }
    cout << sub(ans, cur);
    return 0;
}

using namespace std;
int main(void)
{
    int t, n, m, ans;
    char cij;
    cin >> t;
    while (t--)
    {
        ans = 0;
        cin >> n >> m;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                cin >> cij;
                if (i == n - 1 and j == m - 1)
                    continue;
                if (j == m - 1 and cij != 'D')
                    ++ans;
                else if (i == n - 1 and cij != 'R')
                    ++ans;
            }
        }
        cout << ans << endl;
    }
    return 0;
}