#include <bits/stdc++.h>

using namespace std;

int n;

inline void read() {
	cin >> n;
}

inline void solve() {
	for (int x = 1; x <= 20; x++) {
	    for (int y = 1; y <= 20; y++) {
	        if (x + y >= n || x == y) continue;
	        int z = n - x - y;
	        if (z == x || z == y) continue;
	        if (x % 3 == 0 || y % 3 == 0 || z % 3 == 0) {
	            continue;
	        }
	        puts("YES");
	        cout << x << ' ' << y << ' ' << z << endl;
	        return;
	    }
	}
	puts("NO");
}

int main () {
    int t;
    cin >> t;
    while (t--){
        read();
        solve();
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  auto dist = [](int x1, int y1, int x2, int y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
  };
 
  int t;
  cin >> t;
  while (t--) {
    int px, py, ax, ay, bx, by;
    cin >> px >> py >> ax >> ay >> bx >> by;
    double pa = dist(px, py, ax, ay), pb = dist(px, py, bx, by);
    double oa = dist(0, 0, ax, ay), ob = dist(0, 0, bx, by);
    double ab = dist(ax, ay, bx, by);
    double ans = 1e9;
    ans = min(ans, max(pa, oa));
    ans = min(ans, max(pb, ob));
    ans = min(ans, max({ab / 2, pa, ob}));
    ans = min(ans, max({ab / 2, pb, oa}));
    cout << setprecision(10) << fixed << ans << '\n';
  }
}

#include <bits/stdc++.h>

using namespace std;

const int N = 200000;

int t;

int main() {
    cin >> t;
    for (int tc = 0; tc < t; ++tc) {
        string s;
        long long pos;
        cin >> s >> pos;
        --pos;
        
        int curLen = s.size();
        vector <char> st;
        bool ok = pos < curLen;
        s += '$';
        
        for (auto c : s) {
            while (!ok && st.size() > 0 && st.back() > c) {
                pos -= curLen;
                --curLen;
                st.pop_back();
                
                if(pos < curLen) 
                    ok = true;
            }
            st.push_back(c);
        }
        
        cout << st[pos];
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

const int N = 300009;

int bp(int a, int n) {
    int res = 1;
    while(n > 0) {
        if (n & 1)
            res = (res * 1LL * a) % MOD;
        a = (a * 1LL * a) % MOD;
        n >>= 1;
    }
    return res;
}

int n, m;
string s;
int inv[N];

void upd(int &res, int x) {
    res = (res * 1LL * x) % MOD;
}

int main() {
    inv[1] = 1;
    for (int i = 2; i < N; ++i){
	    inv[i] = bp(i, MOD - 2);
    }
    
    cin >> n >> m >> s;
    
    int res = 1, k = n;
    bool isZero = false;
    for (int i = 0; i < s.size(); ++i) 
        if (s[i] == '?') {
            if (i == 0) {
                isZero = true;
            } else {
                upd(res, i);
            }
        }
    
    cout << (isZero? 0 : res) << endl;
    
    for(int i = 0; i < m; ++i) {
        int pos;
        char c;
        cin >> pos >> c;
        --pos;
        
        if (s[pos] == '?' && (c == '<' || c == '>')) {
            if (pos == 0)
                isZero = false;
            else
                upd(res, inv[pos]);
        } else if ((s[pos] == '<' || s[pos] == '>') && c == '?') {
            if (pos == 0)
                isZero = true;
            else
                upd(res, pos);
        }
        
        s[pos] = c;
        cout << (isZero? 0 : res) << endl;
    }
    return 0;
}

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	vector<int> a(n), b(m);
	forn(i, n) scanf("%d", &a[i]);
	forn(i, m) scanf("%d", &b[i]);
	vector<int> ord(n);
	iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&a](int i, int j){
		return a[i] > a[j];
	});
	vector<vector<int>> mn(m, vector<int>(n + 2));
	forn(i, m){
		int r = 0;
		forn(l, n + 2){
			r = min(n + 1, max(r, l + 1));
			while (r <= n && a[ord[r - 1]] * (r - l) < b[i]) ++r;
			mn[i][l] = r;
		}
	}
	vector<int> dp(1 << m, n + 1);
	dp[0] = 0;
	vector<int> p(1 << m, -1);
	forn(mask, 1 << m) forn(i, m) if (!((mask >> i) & 1) && dp[mask | (1 << i)] > mn[i][dp[mask]]){
		dp[mask | (1 << i)] = mn[i][dp[mask]];
		p[mask | (1 << i)] = mask;
	}
	int mask = (1 << m) - 1;
	if (dp[mask] > n){
		puts("NO");
		return 0;
	}
	puts("YES");
	vector<vector<int>> ans(n);
	forn(_, m){
		int i = __builtin_ctz(mask ^ p[mask]);
		for (int j = dp[p[mask]]; j < dp[mask]; ++j)
			ans[i].push_back(ord[j]);
		mask = p[mask];
	}
	forn(i, m){
		printf("%d", int(ans[i].size()));
		for (int x : ans[i]) printf(" %d", x + 1);
		puts("");
	}
	return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 3003;
 
int n;
int k[4];
vector<int> a[4];
 
struct segtree {
  int sz;
  int tot;
  vector<int> t, p;
  
  segtree(int sz) : sz(sz) {
    tot = 0;
    t = vector<int>(4 * sz);
    p = vector<int>(4 * sz);
    build(0, 0, sz);
  }
  
  void build(int v, int l, int r) {
    if (l + 1 == r) {
      t[v] = -l;
      return;
    }
    int m = (l + r) / 2;
    build(v * 2 + 1, l, m);
    build(v * 2 + 2, m, r);
    t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
  }
  
  void push(int v) {
    if (p[v] == 0) return;
    if (v + 1 < 2 * sz) {
      t[v * 2 + 1] += p[v];
      p[v * 2 + 1] += p[v];
      t[v * 2 + 2] += p[v];
      p[v * 2 + 2] += p[v];
      p[v] = 0;
    }
  } 
  
  void upd(int v, int l, int r, int L, int R, int x) {
    if (L >= R) return;
    if (l == L && r == R) {
      t[v] += x;
      p[v] += x;
      return;
    }
    push(v);
    int m = (l + r) / 2;
    upd(v * 2 + 1, l, m, L, min(m, R), x);
    upd(v * 2 + 2, m, r, max(L, m), R, x);
    t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
  }
  
  void upd(int pos, int x) { 
    tot += x;
    upd(0, 0, sz, max(0, pos), sz, x);
  }
  
  int get(int v, int l, int r, int L, int R) {
    if (L >= R) return -1e9;
    if (l == L && r == R) return t[v];
    push(v);
    int m = (l + r) / 2;
    return max(
      get(v * 2 + 1, l, m, L, min(m, R)),
      get(v * 2 + 2, m, r, max(L, m), R)
    );
  }
  
  int get(int L) {
    return get(0, 0, sz, max(0, L), sz);
  }
  
  int getBad(int v, int l, int r) {
    if (t[v] <= 0) return -1;
    if (l + 1 == r) return l;
    push(v);
    int m = (l + r) / 2;
    if (t[v * 2 + 1] > 0) {
      return getBad(v * 2 + 1, l, m);
    } else {
      return getBad(v * 2 + 2, m, r);
    }
  }
  
  int getBad() {
    return getBad(0, 0, sz);
  }
};  
 
int main() {
  cin >> n;
  int sz = 1;
  for (int i = 0; i < n; ++i) {
    int t, s;
    cin >> t >> s;
    a[t].push_back(s);
    sz = max(sz, s + 1);
  }
  for (int t = 1; t < 4; ++t) {
    sort(a[t].begin(), a[t].end());
    k[t] = a[t].size();
  }
  reverse(a[2].begin(), a[2].end());
  int ans = 1e4;
  for (int len = 1; len <= k[2] + k[3] + 1; ++len) {
    segtree L(sz), R(sz);
    multiset<int> used;
    for (int x : a[1]) L.upd(x, +1);
    for (int x : a[2]) R.upd(x, +1);
    for (int x : a[3]) {
      L.upd(x - len, +1);
      if (L.t[0] <= 0) {
        used.insert(x - len);
      } else {
        L.upd(x - len, -1);
        L.upd(x, +1);
        R.upd(x, +1);
      }
    }
    for (int i = 0; i <= k[2]; ++i) {
      if (L.t[0] <= 0 && R.t[0] <= 0 && R.tot + 1 <= len)
        ans = min(ans, n + (k[3] - (int)used.size()) + 2); 
      if (i == k[2]) break;
      R.upd(a[2][i], -1);
      L.upd(a[2][i] - len, +1);
      int pos;
      while ((pos = L.getBad()) != -1) {
        auto it = used.upper_bound(pos);
        if (it == used.begin()) break;
        --it;
        L.upd(*it, -1);
        L.upd(*it + len, +1);
        R.upd(*it + len, +1);
        used.erase(it);
      }
    }
  }
  if (ans == 1e4) ans = -1;
  cout << ans << '\n';
}