#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define eb emplace_back
 
 
 
void solve() {
    int n; 
    cin >> n;
    for (int a = 3; a < n; a++) {
        int c = (n - a) / 2;
        int b = n - a - c;
        if (c > 1 && b+1 < a) {
            c--;
            b++;
        }
        if (a > b && b > c) {
            cout << b << ' ' << a << ' ' << c << endl;
            return;
        }
    }
}
 
int main() {
    int t;
    cin >> t;
 
    forn(tt, t) {
        solve();
    }
}

#include<bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
const int inf = 1e9 + 7;
 
bool equals(vector<int>&a, vector<int>&b, int n){
    int dif = inf;
    forn(i, n){
        if(b[i] != 0) dif = min(dif, a[i] - b[i]);
    }
    if(dif < 0) return false; 
    if(dif == inf) return true;
    forn(i, n){
        if(a[i] - b[i] > dif) return false;
        if(b[i] != 0 && a[i] - b[i] < dif) return false;
    }
    return true;
}
 
void solve(){
    int n;
    cin >> n;
    vector<int>a(n), b(n);
    forn(i, n) cin >> a[i];
    forn(i, n) cin >> b[i];
    cout << (equals(a, b, n) ? "YES\n" : "NO\n");
 
}
 
int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
 
void solve() {
    int n;
    cin >> n;
    int s[n];
    int f[n];
    for (int i = 0; i < n; ++i) {
        cin >> s[i];
    }
 
    for (int i = 0; i < n; ++i) {
        cin >> f[i];
    }
    int curTime = 0;
    int d[n];
    for (int i = 0; i < n; ++i) {
        curTime = max(curTime, s[i]);
        d[i] = f[i] - curTime;
        curTime = f[i];
    }
    for (auto now: d) {
        cout << now << " ";
    }
    cout << '\n';
}
int main() {
    int tests;
    cin >> tests;
    forn(tt, tests) {
        solve();
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;
        vector<int> w(n + 1);
        for (int i = 1; i <= n; i++)
            w[i] = w[i - 1] + int(s[i - 1] == 'W');
        int result = INT_MAX;
        for (int i = k; i <= n; i++)
            result = min(result, w[i] - w[i - k]);
        cout << result << endl;
    }
}

#include<bits/stdc++.h>
#define len(s) (int)s.size()
using namespace std;
using ll = long long;
 
void solve(){
    int n, k;
    cin >> n >> k;
    vector<ll>a(n);
    ll sum = 0;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i] / k;
        a[i] = a[i] % k;
    }
    sort(a.begin(), a.end(), [] (int x, int y){
        return x > y;
    });
 
    for(int i = 0, j = n - 1; i < j; i++, j--){
        while(a[i] + a[j] < k && i < j) j--;
        if(i == j) break;
        sum++;
    }
    cout << sum << endl;
}
 
int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

def gcd(a, b):
    if b == 0:
        return a;
    return gcd(b, a % b)
    
    
def shift(s):
    for i in range(1, len(s) + 1):
        if s == s[i:] + s[:i]:
            return i
    
 
def solve():
    n = int(input())
    s = input()
    p = [int(x)-1 for x in input().split()]
    used = [False] * n
    ans = 1
    i = 0
    while i < n:
        ss = ''
        while not used[i]:
            ss += s[i]
            used[i] = True
            i = p[i];
        i += 1
        if len(ss) == 0:
            continue
        ln = shift(ss)
        ans = ans * ln // gcd(ans, ln)
    print(ans)
    
 
t = int(input())
for _ in range(t):
    solve()

#include<bits/stdc++.h>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<int> a(n);
        set<int> tmp;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if (tmp.empty() || a[i] < a[*tmp.rbegin()]) {
                tmp.insert(i);
            }
        }
        for (int i = 0; i < m; i++) {
            int j, d;
            cin >> j >> d;
            j--;
            a[j] -= d;
            auto it = tmp.upper_bound(j);
            if (it != tmp.begin()) {
                it = prev(it);
                if (*it == j || a[*it] > a[j]) {
                    tmp.insert(j);
                }
            } else {
                tmp.insert(j);
            }
            while (1) {
                it = tmp.upper_bound(j);
                if (it != tmp.end() && a[*it] >= a[j]) {
                    tmp.erase(it);
                } else {
                    break;
                }
            }
            cout << (int) tmp.size() << " ";
        }
        cout << '\n';
    }
}