#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;


int main() {
	int tc;
	scanf("%d", &tc);
	while (tc--){
		int n;
		scanf("%d", &n);
		int p = 0, c = 0;
		bool fl = true;
		forn(i, n){
			int x, y;
			scanf("%d%d", &x, &y);
			if (x < p || y < c || y - c > x - p)
				fl = false;
			p = x, c = y;
		}
		puts(fl ? "YES" : "NO");
	}
	return 0;
}

fun main() {
    val T = readLine()!!.toInt()
    for (tc in 1..T) {
        val (n, x) = readLine()!!.split(' ').map { it.toInt() }
        val a = readLine()!!.split(' ').map { it.toInt() }.sortedDescending()

        var cnt = 0
        var sum = 0L
        while (cnt < n && sum + a[cnt] >= (cnt + 1) * x.toLong()) {
            sum += a[cnt]
            cnt++
        }
        println(cnt)
    }
}

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); ++i)

typedef long long li;

const int N = 300 * 1000 + 13;

int n;
li a[N], b[N];

void solve() {
	scanf("%d", &n);
	forn(i, n) scanf("%lld%lld", &a[i], &b[i]);
	
	li ans = 0, mn = 1e18;
	forn(i, n) {
		int ni = (i + 1) % n;
		li val = min(a[ni], b[i]);
		ans += a[ni] - val;
		mn = min(mn, val);
	}
	ans += mn;
	printf("%lld\n", ans);
}

int main() {
	int T;
	scanf("%d", &T);
	forn(i, T)
		solve();
}

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

int n;
li l, r;

inline bool read() {
	if(!(cin >> n >> l >> r))
		return false;
	return true;
}

bool intersect(li l1, li r1, li l2, li r2) {
	return min(r1, r2) > max(l1, l2);
}

vector<int> ans;

void calc(int lf, int rg, li &id) {
	if(lf == rg) return;
	
	if(intersect(l, r, id, id + 2 * (rg - lf))) {
		fore(to, lf + 1, rg + 1) {
			if(l <= id && id < r)
				ans.push_back(lf);
			id++;
			
			if(l <= id && id < r)
				ans.push_back(to);
			id++;
		}
	} else
		id += 2 * (rg - lf);
	
	calc(lf + 1, rg, id);
	
	if(lf == 0) {
		if(l <= id && id < r)
			ans.push_back(lf);
		id++;
	}
}

inline void solve() {
	ans.clear();
	li id = 0;
	l--;
	calc(0, n - 1, id);
	
	assert(sz(ans) == r - l);
	assert(id == n * li(n - 1) + 1);
	
	for(int v : ans)
		cout << v + 1 << " ";
	cout << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	int tc; cin >> tc;
	
	while(tc--) {
		read();
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int MOD = 998244353;

int add(int a, int b){
	a += b;
	if (a >= MOD)
		a -= MOD;
	if (a < 0)
		a += MOD;
	return a;
}

int mul(int a, int b){
	return a * 1ll * b % MOD;
}

int binpow(int a, int b){
	int res = 1;
	while (b){
		if (b & 1)
			res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}

int main() {
	long long d;
	scanf("%lld", &d);
	int q;
	scanf("%d", &q);
	
	vector<long long> primes;
	for (long long i = 2; i * i <= d; ++i) if (d % i == 0){
		primes.push_back(i);
		while (d % i == 0) d /= i;
	}
	if (d > 1){
		primes.push_back(d);
	}
	
	vector<int> fact(100), rfact(100);
	fact[0] = 1;
	for (int i = 1; i < 100; ++i)
		fact[i] = mul(fact[i - 1], i);
	rfact[99] = binpow(fact[99], MOD - 2);
	for (int i = 98; i >= 0; --i)
		rfact[i] = mul(rfact[i + 1], i + 1);
	
	forn(i, q){
		long long x, y;
		scanf("%lld%lld", &x, &y);
		vector<int> up, dw;
		for (auto p : primes){
			int cnt = 0;
			while (x % p == 0){
				--cnt;
				x /= p;
			}
			while (y % p == 0){
				++cnt;
				y /= p;
			}
			if (cnt < 0) dw.push_back(-cnt);
			else if (cnt > 0) up.push_back(cnt);
		}
		int ans = 1;
		ans = mul(ans, fact[accumulate(up.begin(), up.end(), 0)]);
		for (auto it : up) ans = mul(ans, rfact[it]);
		ans = mul(ans, fact[accumulate(dw.begin(), dw.end(), 0)]);
		for (auto it : dw) ans = mul(ans, rfact[it]);
		printf("%d\n", ans);
	}
	
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

typedef long long li;
const li INF64 = li(1e18);
const int N = 500043;

li f[N];

li get(int x)
{
    li ans = 0;    
    for (; x >= 0; x = (x & (x + 1)) - 1)
        ans += f[x];
    return ans;
}

void inc(int x, li d)
{
    for (; x < N; x = (x | (x + 1)))
        f[x] += d;    
}

li get(int l, int r)
{
    return get(r) - get(l - 1);
}

li dp[N];
int a[N], b[N], p[N];
int n, m;

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    for(int i = 0; i < n; i++)
        scanf("%d", &p[i]);
    scanf("%d", &m);
    for(int i = 0; i < m; i++)
        scanf("%d", &b[i]);

    for(int i = 0; i < n; i++)
        dp[i] = -INF64;
    map<int, vector<int> > pos;
    for(int i = 0; i < n; i++)
        pos[a[i]].push_back(i);
    set<pair<int, int> > q;
    for(int i = 0; i < n; i++)
        q.insert(make_pair(a[i], i));
    
    for(auto x : pos[b[0]])
        dp[x] = p[x];
    while(!q.empty() && q.begin()->first <= b[0])
    {
        int k = q.begin()->second;
        q.erase(q.begin());
        if(p[k] > 0)
            inc(k, p[k]);
    }  

    for(int i = 1; i < m; i++)
    {
        int i1 = b[i - 1], i2 = b[i];
        vector<int> both_pos;
        for(auto x : pos[i1])
            both_pos.push_back(x);
        for(auto x : pos[i2])
            both_pos.push_back(x);
        li best = -INF64;
        int last = -1;
        sort(both_pos.begin(), both_pos.end());
        for(auto x : both_pos)
        {
            best += get(last + 1, x);
            last = x;
            if(a[x] == i1)
                best = max(best, dp[x]);
            else
                dp[x] = best + p[x];
        }
        while(!q.empty() && q.begin()->first <= i2)
        {
            int k = q.begin()->second;
            q.erase(q.begin());
            if(p[k] > 0)
                inc(k, p[k]);
        }
    }

    li best_dp = -INF64;
    for(int i = 0; i < n; i++)
        if(a[i] == b[m - 1])
            best_dp = max(best_dp, dp[i] + get(i + 1, n - 1));
    li ans = 0;
    for(int i = 0; i < n; i++)
        ans += p[i];
    ans -= best_dp;
    if(ans > li(1e15))
        puts("NO");
    else     
        printf("YES\n%lld\n", ans);
    
}

#include<bits/stdc++.h>

using namespace std;

#define forn(i, n) for(int i = 0; i < n; i++)
#define sz(a) ((int)(a).size())

const int LOGN = 20;
const int N = (1 << LOGN);

typedef long double ld;
typedef long long li;

const ld PI = acos(-1.0);

struct comp 
{
    ld x, y;
    comp(ld x = .0, ld y = .0) : x(x), y(y) {}
    inline comp conj() { return comp(x, -y); }
};

inline comp operator +(const comp &a, const comp &b) 
{
    return comp(a.x + b.x, a.y + b.y);
}

inline comp operator -(const comp &a, const comp &b) 
{
    return comp(a.x - b.x, a.y - b.y);
}

inline comp operator *(const comp &a, const comp &b) 
{
    return comp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}

inline comp operator /(const comp &a, const ld &b) 
{
    return comp(a.x / b, a.y / b);
}

vector<comp> w[LOGN];
vector<int> rv[LOGN];

void precalc() 
{
    for(int st = 0; st < LOGN; st++) 
    {
        w[st].assign(1 << st, comp());
        for(int k = 0; k < (1 << st); k++) 
        {
            double ang = PI / (1 << st) * k;
            w[st][k] = comp(cos(ang), sin(ang));
        }
        
        rv[st].assign(1 << st, 0);
        if(st == 0) 
        {
            rv[st][0] = 0;
            continue;
        }
        int h = (1 << (st - 1));
        for(int k = 0; k < (1 << st); k++)
            rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
    }
}

inline void fft(comp a[N], int n, int ln, bool inv) 
{
    for(int i = 0; i < n; i++) 
    {
        int ni = rv[ln][i];
        if(i < ni)
            swap(a[i], a[ni]);
    }
    
    for(int st = 0; (1 << st) < n; st++) 
    {
        int len = (1 << st);
        for(int k = 0; k < n; k += (len << 1)) 
        {
            for(int pos = k; pos < k + len; pos++) 
            {
                comp l = a[pos];
                comp r = a[pos + len] * (inv ? w[st][pos - k].conj() : w[st][pos - k]);
                
                a[pos] = l + r;
                a[pos + len] = l - r;
            }
        }
    }
    
    if(inv) for(int i = 0; i < n; i++)
        a[i] = a[i] / n;
}

comp aa[N];
comp bb[N];
comp cc[N];

inline void multiply(comp a[N], int sza, comp b[N], int szb, comp c[N], int &szc) 
{
    int n = 1, ln = 0;
    while(n < (sza + szb))
        n <<= 1, ln++;
    for(int i = 0; i < n; i++)
        aa[i] = (i < sza ? a[i] : comp());
    for(int i = 0; i < n; i++)
        bb[i] = (i < szb ? b[i] : comp());
        
    fft(aa, n, ln, false);
    fft(bb, n, ln, false);
    
    for(int i = 0; i < n; i++)
        cc[i] = aa[i] * bb[i];
        
    fft(cc, n, ln, true);
    
    szc = n;
    for(int i = 0; i < n; i++)
        c[i] = cc[i];
}

comp a[N];
comp b[N];
comp c[N];

vector<int> p_function(const vector<int>& v)
{
    int n = v.size();
    vector<int> p(n);
    for(int i = 1; i < n; i++)
    {
        int j = p[i - 1];
        while(j > 0 && v[j] != v[i])
            j = p[j - 1];
        if(v[j] == v[i])
            j++;
        p[i] = j;   
    }
    return p;
}

int p[26];
char buf[N];
string s, t;

int main()
{
    precalc();                  
    for(int i = 0; i < 26; i++)
    {
        scanf("%d", &p[i]);
        p[i]--;
    }
    scanf("%s", buf);
    s = buf;
    scanf("%s", buf);
    t = buf;

    int n = s.size();
    int m = t.size();
    vector<int> color(26, 0);
    vector<vector<int> > cycles;
    for(int i = 0; i < 26; i++)
    {
        if(color[i])
            continue;
        vector<int> cycle;
        int cc = cycles.size() + 1;
        int cur = i;
        while(color[cur] == 0)
        {
            cycle.push_back(cur);
            color[cur] = cc;
            cur = p[cur];
        }
        cycles.push_back(cycle);
    }

    vector<int> ans(m - n + 1);
    vector<int> s1, t1;
    for(int i = 0; i < n; i++)
        s1.push_back(color[int(s[i] - 'a')]);
    for(int i = 0; i < m; i++)
        t1.push_back(color[int(t[i] - 'a')]);
    vector<int> st = s1;
    st.push_back(0);
    for(auto x : t1)
        st.push_back(x);
    vector<int> pf = p_function(st);
    for(int i = 0; i < m - n + 1; i++)
        if(pf[2 * n + i] == n)
            ans[i] = 1;
    map<char, comp> m1, m2;
    for(auto cur : cycles)
    {
        int k = cur.size();
        for(int i = 0; i < k; i++)
        {
            ld ang1 = 2 * PI * i / k;
            ld ang2 = (PI - 2 * PI * i) / k;
            m1[char('a' + cur[i])] = comp(cosl(ang1), sinl(ang1));
            m2[char('a' + cur[i])] = comp(cosl(ang2), sinl(ang2));
        }
    }

    ld ideal = 0;
    for(int i = 0; i < n; i++)
        ideal += (m1[s[i]] * m2[s[i]]).x;
    reverse(s.begin(), s.end());
    for(int i = 0; i < n; i++)                  
        a[i] = m1[s[i]];                
    for(int i = 0; i < m; i++)
        b[i] = m2[t[i]];
    int szc;
    multiply(a, n, b, m, c, szc);
    for(int i = 0; i < m - n + 1; i++)
        if(fabsl(c[i + n - 1].x - ideal) > 0.01)
            ans[i] = 0;
    

    for(int i = 0; i < m - n + 1; i++)
        printf("%d", ans[i]);
    return 0;
}

for i in range(int(input())):
    n, k = map(int, input().split())
    print('YES' if k * k <= n and n % 2 == k % 2 else 'NO')

from sys import stdin, stdout

t = int(stdin.readline())
for _ in range(t):
    n = int(stdin.readline())
    used = [False for i in range(n)]
    v = -1
    for i in range(n):
        l = [int(x) - 1 for x in stdin.readline().split()][1:]
        for j in l:
            if not used[j]:
                used[j] = True
                break
        else:
            v = i
    if v == -1:
        stdout.write("OPTIMAL\n")
    else:
        u = used.index(False)
        stdout.write("IMPROVE\n" + str(v + 1) + " " + str(u + 1) + "\n")

n, m, _ = map(int, input().split())

print(2 * (n - 1) + (n + 1) * (m - 1))
print("U" * (n - 1) + "L" * (m - 1), end="")
for i in range(n):
    if i != 0:
        print("D", end="")
    if i % 2 == 0:
        print("R" * (m - 1), end="")
    else:
        print("L" * (m - 1), end="")

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;
typedef pair<int, int> pt;

const int INF = int(1e9);
const li INF64 = li(1e18);

int n;
vector<int> p, c;

inline bool read() {
    if(!(cin >> n))
        return false;
    p.resize(n);
    c.resize(n);
    
    fore(i, 0, n) {
        cin >> p[i];
        p[i]--;
    }
    fore(i, 0, n)
        cin >> c[i];
    return true;
}

inline void solve() {
    vector<int> used(n, 0);
    
    int ans = INF;
    fore(st, 0, n) {
        if(used[st])
            continue;
        
        vector<int> cycle;
        int v = st;
        while(!used[v]) {
            used[v] = 1;
            cycle.push_back(v);
            v = p[v];
        }
        
        fore(step, 1, sz(cycle) + 1) {
            if(sz(cycle) % step != 0)
                continue;
            
            fore(s, 0, step) {
                bool eq = true;
                for(int pos = s; pos + step < sz(cycle); pos += step) {
                    if(c[cycle[pos]] != c[cycle[pos + step]])
                        eq = false;
                }
                if(eq) {
                    ans = min(ans, step);
                    break;
                }
            }
        }
    }
    cout << ans << endl;
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);
    
    int tc; cin >> tc;
    
    while(tc--) {
        read();
        solve();
        
#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}

MOD = 998244353
p = [1] * 200005
for i in range(1, 200005):
    p[i] = (p[i - 1] * 10) % MOD

n = int(input())
for i in range(1, n):
    res = 2 * 10 * 9 * p[n - i - 1]
    res += (n - 1 - i) * 10 * 9 * 9 * p[n - i - 2]
    print(res % MOD, end = ' ')
print(10)

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)

typedef pair<int, int> pt;

const int MOD = 998244353;
const int N = 500 * 1000 + 13;

int n, k, m;
pair<pt, int> q[N];

int ones[N];
int mx[N], sum[N];

int add(int x, int y) {
    x += y;
    if (x >= MOD) x -= MOD;
    if (x < 0) x += MOD;
    return x;
}

int calc(int t) {
    memset(ones, 0, sizeof(ones));
    memset(mx, -1, sizeof(mx));
    
    forn(i, m) {
        int l = q[i].x.x, r = q[i].x.y;
        if (q[i].y & (1 << t)) {
            ones[l]++;
            ones[r + 1]--;
        } else {
            mx[r] = max(mx[r], l);
        }
    }
    
    int j = -1;
    forn(i, n) {
        int cur = 0;
        if (!ones[i]) {
            cur = sum[i];
            if (j == -1) cur = add(cur, 1);
            else cur = add(cur, -sum[j]);
        }
        
        sum[i + 1] = add(sum[i], cur);
        ones[i + 1] += ones[i];
        j = max(j, mx[i]);
    }
    
    return add(sum[n], j != -1 ? -sum[j] : 1);
}

int main() {
    scanf("%d%d%d", &n, &k, &m);
    forn(i, m) {
        scanf("%d%d%d", &q[i].x.x, &q[i].x.y, &q[i].y);
        --q[i].x.x; --q[i].x.y;
    }
    
    int ans = 1;
    forn(i, k) ans = (ans * 1ll * calc(i)) % MOD;
    printf("%d\n", ans);
}

#include<bits/stdc++.h>

using namespace std;

const int N = 8000043;
const int K = 15;
const int M = 1043;

int k;
char buf[N], buf2[M];
vector<string> t;
vector<int> c;
string s;

map<char, int> nxt[M];
int lnk[M];
int p[M];
char pchar[M];
map<char, int> go[M];
int term[M];
int ts = 1;
int A[M][K];
int F[M][K];
int dp[M];

int get_nxt(int x, char c)
{
    if(!nxt[x].count(c))
    {
        p[ts] = x;
        pchar[ts] = c;
        nxt[x][c] = ts++;
    }
    return nxt[x][c];
}

void add_string(int i)
{
    int cur = 0;
    for(auto x : t[i])
    {
        cur = get_nxt(cur, x);
    }
    term[cur] += c[i];
}

int get_go(int x, char c);

int get_lnk(int x)
{
    if(lnk[x] != -1)
        return lnk[x];
    if(x == 0 || p[x] == 0)
        return lnk[x] = 0;
    return lnk[x] = get_go(get_lnk(p[x]), pchar[x]);
}

int get_dp(int x)
{
    if(dp[x] != -1)
        return dp[x];
    dp[x] = term[x];
    if(get_lnk(x) != x)
        dp[x] += get_dp(get_lnk(x));
    return dp[x];
}

int get_go(int x, char c)
{
    if(go[x].count(c))
        return go[x][c];
    if(nxt[x].count(c))
        return go[x][c] = nxt[x][c];
    if(x == 0)
        return go[x][c] = 0;
    return go[x][c] = get_go(get_lnk(x), c);
}

void build_skip(const string& s, vector<int>& sA, vector<long long>& sF)
{                     
    sA = vector<int>(ts);
    for(int i = 0; i < ts; i++)
        sA[i] = i;
    sF = vector<long long>(ts);
    for(auto c : s)
    {
        int ci = int(c - 'a');
        for(int i = 0; i < ts; i++)
        {
            sF[i] += F[sA[i]][ci];
            sA[i] = A[sA[i]][ci];
        }
    }
}

long long solve(const string& s)
{
    long long BAD = (long long)(-1e18);

    vector<int> pos;
    for(int i = 0; i < s.size(); i++)
        if(s[i] == '?')
            pos.push_back(i);
    int cntQ = pos.size();
    vector<vector<int> > skip_A(cntQ + 1);
    vector<vector<long long> > skip_F(cntQ + 1);
    build_skip(s.substr(0, pos[0]), skip_A[0], skip_F[0]);
    for(int i = 1; i < cntQ; i++)
        build_skip(s.substr(pos[i - 1] + 1, pos[i] - pos[i - 1] - 1), skip_A[i], skip_F[i]);
    build_skip(s.substr(pos.back() + 1, s.size() - pos.back() - 1), skip_A[cntQ], skip_F[cntQ]);

    vector<vector<long long> > dp(1 << (K - 1), vector<long long>(ts, BAD));
    vector<int> used(1 << K);
    dp[0][skip_A[0][0]] = skip_F[0][0];
    queue<int> q;
    q.push(0);
    used[0] = 1;
    long long ans = BAD;
    while(!q.empty())
    {
        int k = q.front();
        q.pop();
        int step = __builtin_popcount(k);
        if(step == cntQ)
        {
            for(int i = 0; i < ts; i++)
                ans = max(ans, dp[k][i]);
            continue;
        }
        for(int i = 0; i < K - 1; i++)
        {
            if(k & (1 << i)) continue;
            int nk = (k ^ (1 << i));
            if(used[nk] == 0)
            {
                used[nk] = 1;
                q.push(nk);
            }
            for(int j = 0; j < ts; j++)
            {
                if(dp[k][j] == BAD)
                    continue;
                int nj = get_go(j, char('a' + i));
                int newSt = skip_A[step + 1][nj];
                long long add = get_dp(nj) + skip_F[step + 1][nj];
                dp[nk][newSt] = max(dp[nk][newSt], dp[k][j] + add);
            }
        }
    }
    return ans;
}

int main()
{
    scanf("%d", &k);
    t.resize(k);
    c.resize(k);
    for(int i = 0; i < k; i++)
    {
        scanf("%s %d", buf2, &c[i]);
        t[i] = buf2;
    }    
    scanf("%s", buf);
    s = buf;

    for(int i = 0; i < k; i++)
        add_string(i);
    for(int i = 0; i < ts; i++)
    {
        lnk[i] = -1;
        dp[i] = -1;
    }
    for(int i = 0; i < ts; i++)
    {
        get_lnk(i);
        for(char c = 'a'; c <= 'o'; c++)
            get_go(i, c);
    }
    for(int i = 0; i < ts; i++)
        get_dp(i);                               
    for(int i = 0; i < ts; i++)
    {
        for(int j = 0; j < K; j++)
        {
            A[i][j] = get_go(i, char('a' + j));
            F[i][j] = dp[A[i][j]];
        }
    }   
    int n = s.size();
    vector<int> leftQ(n, -1);
    vector<int> rightQ(n, -1);
    for(int i = 0; i < n; i++)
    {
        if(i != 0)
            leftQ[i] = leftQ[i - 1];
        if(s[i] == '?')
            leftQ[i] = i;
    }
    for(int i = n - 1; i >= 0; i--)
    {
        if(i != n - 1)
            rightQ[i] = rightQ[i + 1];
        if(s[i] == '?')
            rightQ[i] = i;
    }
    vector<int> bad(n, 0);
    
    if(leftQ.back() == -1)
        bad = vector<int>(n, 1);

    long long ans = 0;
    int curSt = 0;
    string news = "";
    for(int i = 0; i < n; i++)
    {
        int ci = (s[i] == '?' ? 14 : int(s[i] - 'a'));
        if(bad[i])
            ans += F[curSt][ci];
        curSt = A[curSt][ci];
        if(!bad[i])
            news.push_back(s[i]);
        else if(i != 0 && !bad[i - 1])
            news.push_back('o');
    }                    
    if(!news.empty())
        ans += solve(news);
    printf("%lld\n", ans);
}

for i in range(int(input())):
    n, m = map(int, input().split())
    print('YES' if n % m == 0 else 'NO')

for t in range(int(input())):
    n = input()
    print(*sorted(map(int, input().split()))[::-1])

fun main() {
    val T = readLine()!!.toInt()
    testCases@for (tc in 1..T) {
        val (_, k) = readLine()!!.split(' ').map { it.toLong() }
        val a = readLine()!!.split(' ').map { it.toLong() }.toLongArray()

        var maxPower = 1L
        while (maxPower < 1e16.toLong())
            maxPower *= k

        while (maxPower > 0) {
            val positions = a.withIndex().filter { it.value >= maxPower }.map { it.index }
            if (positions.isNotEmpty()) {
                if (positions.size > 1) {
                    println("NO")
                    continue@testCases
                }
                a[positions[0]] -= maxPower
            }
            maxPower /= k
        }
        if (a.max()!! > 0L) {
            println("NO")
            continue@testCases
        }
        println("YES")
    }
}

fun getMask(a: Long, k: Long): Long? {
    var (tmp, res) = listOf(a, 0L)
    var cnt = 0
    while (tmp > 0) {
        if (tmp % k > 1)
            return null
        res = res or ((tmp % k) shl cnt)
        tmp /= k
        cnt++
    }
    return res
}

fun main() {
    val T = readLine()!!.toInt()
    for (tc in 1..T) {
        val (n, k) = readLine()!!.split(' ').map { it.toLong() }
        val a = readLine()!!.split(' ').map { getMask(it.toLong(), k) }
        val b = a.filterNotNull()
        if (b.size < n) {
            println("NO")
            continue
        } else {
            val res = b.reduce { acc, l -> if (acc < 0 || (acc and l) > 0) -1 else acc or l }
            println(if (res < 0) "NO" else "YES")
        }
    }
}

#include <bits/stdc++.h>

using namespace std;

const int N = 200043;
const int MOD = 998244353;

int add(int x, int y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}

int mul(int x, int y)
{
    return (x * 1ll * y) % MOD;
}

int binpow(int x, int y)
{
    int z = 1;
    while(y)
    {
        if(y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}

int inv(int x)
{
    return binpow(x, MOD - 2);
}

int divide(int x, int y)
{
    return mul(x, inv(y));
}

int fact[N];

void precalc()
{
    fact[0] = 1;
    for(int i = 1; i < N; i++)
        fact[i] = mul(fact[i - 1], i);
}

int C(int n, int k)
{
    return divide(fact[n], mul(fact[k], fact[n - k]));
}

int main() 
{
    precalc();
    int n, m;
    cin >> n >> m;
    int ans = 0;
    if(n > 2)
        ans = mul(C(m, n - 1), mul(n - 2, binpow(2, n - 3)));
    cout << ans << endl;
}

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    out << "[";
    fore(i, 0, sz(v)) {
        if(i) out << ", ";
        out << v[i];
    }
    return out << "]";
}

const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;

const int N = 555;
int n, a[N];

inline bool read() {
    if(!(cin >> n))
        return false;
    fore(i, 0, n)
        cin >> a[i];
    return true;
}

int dp[N][N];

int calcDP(int l, int r) {
    assert(l < r);
    if(l + 1 == r)
        return dp[l][r] = a[l];
    if(dp[l][r] != 0)
        return dp[l][r];
    
    dp[l][r] = -1;
    fore(mid, l + 1, r) {
        int lf = calcDP(l, mid);
        int rg = calcDP(mid, r);
        if(lf > 0 && lf == rg)
            return dp[l][r] = lf + 1;
    }
    return dp[l][r];
}

int dp2[N];

inline void solve() {
    fore(i, 0, N)
        dp2[i] = INF;
    
    dp2[0] = 0;
    fore(i, 0, n) {
        fore(j, i + 1, n + 1) {
            if(calcDP(i, j) > 0)
                dp2[j] = min(dp2[j], dp2[i] + 1);
        }
    }
    cout << dp2[n] << endl;
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);
    
    if(read()) {
        solve();
        
#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 300043;
const int K = 5;

int x, y, z, n;
long long a[N];

typedef vector<vector<int> > state;
map<state, int> d;
int cnt;
int p;
vector<vector<int> > state_log;

int mex(const vector<int>& a)
{
    for(int i = 0; i < a.size(); i++)
    {
        bool f = false;
        for(auto x : a)
            if(x == i)
                f = true;
        if(!f)
            return i;
    }
    return a.size();
}

state go(state s)
{
    int f1 = mex({s[0][K - x], s[1][K - y], s[2][K - z]});
    int f2 = mex({s[0][K - x], s[2][K - z]});
    int f3 = mex({s[0][K - x], s[1][K - y]});
    state nw = s;
    nw[0].push_back(f1);
    nw[1].push_back(f2);
    nw[2].push_back(f3);
    for(int i = 0; i < 3; i++)
        nw[i].erase(nw[i].begin());
    return nw;
}

void precalc()
{
    d.clear();
    state cur(3, vector<int>(K, 0));
    cnt = 0;
    state_log.clear();
    while(!d.count(cur))
    {
        d[cur] = cnt;
        state_log.push_back({cur[0].back(), cur[1].back(), cur[2].back()});
        cur = go(cur);
        cnt++;
    }                   
    p = cnt - d[cur];
}

int get_grundy(long long x, int t)
{
    if(x < cnt)
        return state_log[x][t];
    else
    {
        int pp = cnt - p;
        x -= pp;
        return state_log[pp + (x % p)][t];
    }
}

void read()
{
    scanf("%d %d %d %d", &n, &x, &y, &z);
    for(int i = 0; i < n; i++)
        scanf("%lld", &a[i]);
}                    

int check(int x, int y)
{
    return x == y ? 1 : 0;
}

void solve()
{
    precalc();
    int ans = 0;
    for(int i = 0; i < n; i++)
        ans ^= get_grundy(a[i], 0);
    int res = 0;
    for(int i = 0; i < n; i++)
    {
        ans ^= get_grundy(a[i], 0);
        res += check(ans, get_grundy(max(0ll, a[i] - x), 0));
        res += check(ans, get_grundy(max(0ll, a[i] - y), 1));
        res += check(ans, get_grundy(max(0ll, a[i] - z), 2));
        ans ^= get_grundy(a[i], 0);
    }
    printf("%d\n", res);
}

int main()
{
    int t;
    scanf("%d", &t);
    for(int i = 0; i < t; i++)
    {
        read();
        solve();
    }
}

#include<bits/stdc++.h>

using namespace std;

const int N = 1000043;

map<char, int> nxt[N];
bool term[N];
int n, k;
char buf[3];
int dp[N];
int dict[N];

int T[4 * N];
int f[4 * N];

void build(int v, int l, int r)
{
    T[v] = int(1e9);
    if(l != r - 1)
    {
        int m = (l + r) / 2;
        build(v * 2 + 1, l, m);
        build(v * 2 + 2, m, r);
    }
}

int getVal(int v)
{
    return T[v] + f[v];
}

void push(int v, int l, int r)
{
    T[v] += f[v];
    if(l != r - 1)
    {
        f[v * 2 + 1] += f[v];
        f[v * 2 + 2] += f[v];
    }
    f[v] = 0;
}

void upd(int v, int l, int r)
{
    if(l != r - 1)
    {
        T[v] = min(getVal(v * 2 + 1), getVal(v * 2 + 2));
    }
}

int get(int v, int l, int r, int L, int R)
{
    if(L >= R)
        return int(1e9);
    if(l == L && r == R)
        return getVal(v);
    push(v, l, r);
    int m = (l + r) / 2;
    int ans = min(get(v * 2 + 1, l, m, L, min(m, R)), get(v * 2 + 2, m, r, max(L, m), R));
    upd(v, l, r);
    return ans;
}

void add(int v, int l, int r, int L, int R, int val)
{
    if(L >= R)
        return;
    if(l == L && r == R)
    {
        f[v] += val;
        return;
    }
    push(v, l, r);
    int m = (l + r) / 2;
    add(v * 2 + 1, l, m, L, min(m, R), val);
    add(v * 2 + 2, m, r, max(L, m), R, val);
    upd(v, l, r);
}

void setVal(int v, int l, int r, int pos, int val)
{
    if(l == r - 1)
    {
        f[v] = 0;
        T[v] = val;
        return;
    }
    push(v, l, r);
    int m = (l + r) / 2;
    if(pos < m)
        setVal(v * 2 + 1, l, m, pos, val);
    else
        setVal(v * 2 + 2, m, r, pos, val);
    upd(v, l, r);
}

void dfs(int v, int d, int last)
{
    dp[v] = last + 1;
    if(term[v])
        dp[v] = min(dp[v], get(0, 0, n + 1, 0, d));
    setVal(0, 0, n + 1, d, dp[v] + 1);
    if(term[v])
        add(0, 0, n + 1, 0, d + 1, 1);
    for(auto x : nxt[v])
        dfs(x.second, d + 1, dp[v]);
    setVal(0, 0, n + 1, d, int(1e9));
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        int p;
        scanf("%d %s", &p, buf);
        char c = buf[0];
        nxt[p][c] = i + 1;
    }
    scanf("%d", &k);
    for(int i = 0; i < k; i++)
    {
        scanf("%d", &dict[i]);
        term[dict[i]] = true;
    }

    build(0, 0, n + 1);
    dfs(0, 0, -1);
    for(int i = 0; i < k; i++)
        printf("%d ", dp[dict[i]]);
    puts("");
}

for t in range(int(input())):
    print(input().strip('0').count('0'))

fun main() {
    val t = readLine()!!.toInt()
    for (tc in 1..t) {
        val (n, g, b) = readLine()!!.split(' ').map { it.toLong() }
        
        val needG = (n + 1) / 2
        var totalG = needG / g * (b + g)
        totalG += if (needG % g == 0L) -b else needG % g
        println(maxOf(n, totalG))
    }
}

#include <bits/stdc++.h>

using namespace std;

#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)

void solve() {
    string s;
    cin >> s;

    vector<bool> used(26);
    used[s[0] - 'a'] = true;
    string t(1, s[0]);
        
    int pos = 0;
    for (int i = 1; i < sz(s); i++) {
        if (used[s[i] - 'a']) {
            if (pos > 0 && t[pos - 1] == s[i]) {
                pos--;
            } else if (pos + 1 < sz(t) && t[pos + 1] == s[i]) {
                pos++;
            } else {
                cout << "NO" << endl;
                return;
            }
        } else {
            if (pos == 0) {
                t = s[i] + t;
            } else if (pos == sz(t) - 1) {
                t += s[i];
                pos++;
            } else {
                cout << "NO" << endl;
                return;
            }
        }
        used[s[i] - 'a'] = true;
    }
        
    forn(i, 26) if (!used[i])
        t += char(i + 'a');
    cout << "YES" << endl << t << endl;
}

int main() {
    int tc;
    cin >> tc;
    
    forn(i, tc) solve();
}

from math import log2

for t in range(int(input())):
    n, m = map(int, input().split())
    c = [0] * 61
    s = 0
    for x in map(int, input().split()):
        c[int(log2(x))] += 1
        s += x

    if s < n:
        print(-1)
        continue

    i, res = 0, 0
    while i < 60:
        if (1<<i)&n != 0:
            if c[i] > 0:
                c[i] -= 1
            else:
                while i < 60 and c[i] == 0:
                    i += 1
                    res += 1
                c[i] -= 1
                continue
        c[i + 1] += c[i] // 2
        i += 1

    print(res)

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;
typedef pair<int, int> pt;

const int INF = int(1e9);
const li INF64 = li(1e18);

string s, t;

inline bool read() {
    if(!(cin >> s >> t))
        return false;
    for(auto &c : s)
        c -= 'a';
    for(auto &c : t)
        c -= 'a';
    return true;
}

vector< vector<int> > nxt;

bool calc(const string &a, const string &b) {
    vector< vector<int> > dp(sz(a) + 1, vector<int>(sz(b) + 1, INF));
    dp[0][0] = 0;
    fore(i, 0, sz(a) + 1) fore(j, 0, sz(b) + 1) {
        if(dp[i][j] > sz(s))
            continue;
        
        int len = dp[i][j];
        if(i < sz(a) && nxt[len][a[i]] < INF) {
            dp[i + 1][j] = min(dp[i + 1][j], nxt[len][a[i]] + 1);
        }
        if(j < sz(b) && nxt[len][b[j]] < INF) {
            dp[i][j + 1] = min(dp[i][j + 1], nxt[len][b[j]] + 1);
        }
    }
    return dp[sz(a)][sz(b)] < INF;
}

inline void solve() {
    nxt.assign(sz(s) + 1, vector<int>(26, INF));
    for(int i = sz(s) - 1; i >= 0; i--) {
        nxt[i] = nxt[i + 1];
        nxt[i][s[i]] = i;
    }
    
    for(int i = 0; i < sz(t); i++) {
        if(calc(t.substr(0, i), t.substr(i, sz(t)))) {
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << endl;
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);
    
    int tc; cin >> tc;
    
    while(tc--) {
        read();
        solve();
        
#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define pb push_back
#define mp make_pair
#define sqr(a) ((a) * (a))
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i < int(r); ++i)
#define forr(i, r, l) for (int i = int(r) - 1; i >= int(l); --i)

typedef pair<int, int> pt;

const int M = 310;
const int N = 2000 * 1000 + 13;

int n, m, q;
int a[M][M];

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};

bool in(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}

int p[M * M], rk[M * M];

int getp(int v) {
    return p[v] == v ? v : p[v] = getp(p[v]);
}

bool unite(int a, int b) {
    a = getp(a); b = getp(b);
    if (a == b) return false;
    if (rk[a] < rk[b]) swap(a, b);
    p[b] = a;
    rk[a] += rk[b];
    return true;
}

int dif[N];
vector<pt> add[N], del[N];

void recalc(const vector<pt>& ev, int coeff)  {
    forn(i, n) forn(j, m) a[i][j] = 0;
    forn(i, n * m) p[i] = i, rk[i] = 1;
        
    for (auto it : ev) {
        int cur = 1;
        int x = it.x / m, y = it.x % m;
        a[x][y] = 1;
        
        forn(k, 4) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (in(nx, ny) && a[nx][ny] == 1)
                cur -= unite(nx * m + ny, x * m + y);
        }
        
        dif[it.y] += cur * coeff;
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &q);
    int clrs = 1;
    forn(i, q) {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        --x; --y;
        if (a[x][y] == c) continue;
        clrs = c + 1;
        add[c].pb(mp(x * m + y, i));
        del[a[x][y]].pb(mp(x * m + y, i));
        a[x][y] = c;
    }
    
    forn(x, n) forn(y, m)
        del[a[x][y]].pb(mp(x * m + y, q));
    
    forn(i, clrs) reverse(all(del[i]));
    
    forn(i, clrs) recalc(add[i], +1);
    forn(i, clrs) recalc(del[i], -1);
    
    int cur = 1;
    forn(i, q) {
        cur += dif[i];
        printf("%d\n", cur);
    }
}

#include<bits/stdc++.h>

using namespace std;

const int N = 150043;

typedef pair<long long, long long> func;

func T[4 * N];
bool usedT[4 * N];

void clear(int v, int l, int r)
{
    if(!usedT[v]) return;
    usedT[v] = false;
    T[v] = make_pair(0ll, 0ll);
    if(l < r - 1)
    {
        int m = (l + r) / 2;
        clear(v * 2 + 1, l, m);
        clear(v * 2 + 2, m, r);
    }
}

long long eval(func f, int x)
{
    return f.first * x + f.second;
}

long long get(int v, int l, int r, int x)
{
    long long ans = eval(T[v], x);
    if(l < r - 1)
    {
        int m = (l + r) / 2;
        if(m > x)
            ans = max(ans, get(v * 2 + 1, l, m, x));
        else
            ans = max(ans, get(v * 2 + 2, m, r, x));
    }
    return ans;
}

void upd(int v, int l, int r, func f)
{
    usedT[v] = true;
    int m = (l + r) / 2;
    bool need_swap = eval(f, m) > eval(T[v], m);
    if(need_swap)
        swap(T[v], f);
    if(l == r - 1)
        return;
    if(eval(f, l) > eval(T[v], l))
        upd(v * 2 + 1, l, m, f);
    else
        upd(v * 2 + 2, m, r, f);
}

long long ans = 0;

void update_ans(vector<vector<func> > heads, vector<vector<func> > tails)
{
    int n = heads.size();
    for(int i = 0; i < n; i++)
    {
        for(auto x : heads[i])
            ans = max(ans, get(0, 0, N, x.first) + x.second);
        for(auto x : tails[i])
            upd(0, 0, N, x);
    }
    clear(0, 0, N);
}

int a[N];
vector<int> g[N];
int n;
bool used[N];
int siz[N];

void dfs1(int x, int p = -1)
{
    if(used[x]) return;
    siz[x] = 1;
    for(auto to : g[x])
    {                    
        if(!used[to] && to != p)
        {
            dfs1(to, x);
            siz[x] += siz[to];
        }
    }
}

pair<int, int> c;
int S = 0;

void find_centroid(int x, int p = -1)
{
    if(used[x]) return;
    int mx = 0;
    for(auto to : g[x])
    {
        if(!used[to] && to != p)
        {
            find_centroid(to, x);
            mx = max(mx, siz[to]);
        }
    }
    if(p != -1)
        mx = max(mx, S - siz[x]);
    c = min(c, make_pair(mx, x));
}

void dfs_heads(int v, int p, int cnt, long long cursum, long long curadd, vector<func>& sink)
{
    if(used[v])
        return;
    cnt++;
    curadd += a[v];
    cursum += curadd;
    sink.push_back(make_pair(cnt, cursum));
    for(auto to : g[v])
        if(to != p)
            dfs_heads(to, v, cnt, cursum, curadd, sink);
}

void dfs_tails(int v, int p, int cnt, long long cursum, long long curadd, vector<func>& sink)
{
    if(used[v])
        return;
    cnt++;
    curadd += a[v];
    cursum += a[v] * 1ll * cnt;
    sink.push_back(make_pair(curadd, cursum));
    for(auto to : g[v])
        if(to != p)
            dfs_tails(to, v, cnt, cursum, curadd, sink);
}

void centroid(int v)
{
    if(used[v]) return;
    dfs1(v);
    S = siz[v];
    c = make_pair(int(1e9), -1);
    find_centroid(v);
    int C = c.second;
    used[C] = 1;
    vector<vector<func> > heads, tails;
    for(auto to : g[C])
        if(!used[to])
        {
            heads.push_back(vector<func>());
            dfs_heads(to, C, 1, a[C], a[C], heads.back());
            tails.push_back(vector<func>());
            dfs_tails(to, C, 0, 0, 0, tails.back());
        }
    heads.push_back(vector<func>({{1, a[C]}}));
    tails.push_back(vector<func>({{0, 0}}));
    update_ans(heads, tails);
    reverse(heads.begin(), heads.end());
    reverse(tails.begin(), tails.end());
    update_ans(heads, tails);
    for(auto to : g[C])
        centroid(to);
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n - 1; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        --x;
        --y;
        g[x].push_back(y);
        g[y].push_back(x);    
    }
    for(int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    centroid(0);
    printf("%lld\n", ans);
}

t = int(input())
for i in range(t):
    n = int(input())
    if(n % 2 == 1):
        print(7, end='')
        n -= 3
    while(n > 0):
        print(1, end='')
        n -= 2
    print()

#include<bits/stdc++.h>

using namespace std;

typedef long long li;

int n, x;
string s;

inline bool read() {
	if(!(cin >> n >> x >> s))
		return false;
	return true;
}

inline void solve() {
	int ans = 0;
	bool infAns = false;
	
	int cntZeros = (int)count(s.begin(), s.end(), '0');
	int total = cntZeros - (n - cntZeros);
	
	int bal = 0;
	for(int i = 0; i < n; i++) {
		if(total == 0) {
			if(bal == x)
				infAns = true;
		}
		else if(abs(x - bal) % abs(total) == 0) {
			if((x - bal) / total >= 0)
				ans++;
		}
		
		if(s[i] == '0')
			bal++;
		else
			bal--;
	}
	
	if(infAns) ans = -1;
	cout << ans << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	int tc; cin >> tc;
	while(tc--) {
		read();
		solve();
	}
	
	return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int N = int(2e5) + 99;
const int INF = int(1e9) + 99;

int tc;
string s, t;
int nxt[N][26];

int main() {
    cin >> tc;
    while(tc--){
        cin >> s >> t;
        for(int i = 0; i < s.size() + 5; ++i)
            for(int j = 0; j < 26; ++j)
                nxt[i][j] = INF;
    	
        for(int i = int(s.size()) - 1; i >= 0; --i){
            for(int j = 0; j < 26; ++j)
                nxt[i][j] = nxt[i + 1][j];
            nxt[i][s[i] - 'a'] = i;
        }    
    
        int res = 1, pos = 0;
        for(int i = 0; i < t.size(); ++i){
            if(pos == s.size()){
                pos = 0;
                ++res;
            }
            if(nxt[pos][t[i] - 'a'] == INF){
                pos = 0; 
                ++res;
    		}
    		if(nxt[pos][t[i] - 'a'] == INF && pos == 0){
                res = INF;
                break;
            }    
            pos = nxt[pos][t[i] - 'a'] + 1;
            
        }
    
        if(res >= INF) cout << -1 << endl;
        else cout << res << endl;
    }
    return 0;
}

fun gcd(a : Long, b : Long) : Long {
    return if (a == 0L) b else gcd(b % a, a)
}
fun phi(a : Long) : Long {
    var (tmp, ans) = listOf(a, a)
    var d = 2L
    while (d * d <= tmp) {
        var cnt = 0
        while (tmp % d == 0L) {
            tmp /= d
            cnt++
        }
        if (cnt > 0) ans -= ans / d
        d++
    }
    if (tmp > 1L) ans -= ans / tmp
    return ans
}

fun main() {
    val t = readLine()!!.toInt()
    for (tc in 1..t) {
        val (a, m) = readLine()!!.split(' ').map { it.toLong() }
        println(phi(m / gcd(a, m)))
    }
}

#include<bits/stdc++.h>
using namespace std;

const int N = int(2e5) + 99;

int n;
int p[N];
int rp[N];
int a[N];

long long b[N];
long long t[4 * N];
long long add[4 * N];

void build(int v, int l, int r){
	if(r - l == 1){
		t[v] = b[l];
		return;
	}

	int mid = (l + r) / 2;	
	build(v * 2 + 1, l, mid);
	build(v * 2 + 2, mid, r);
	t[v] = min(t[v * 2 + 1], t[v * 2 + 2]); 
}

void push(int v, int l, int r){
	if(add[v] != 0){
		if(r - l > 1)
			for(int i = v+v+1; i < v+v+3; ++i){
				add[i] += add[v];
				t[i] += add[v];
			}
		add[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){
		add[v] += x;
		t[v] += x;
		push(v, l, r);
		return;
	}
	
	push(v, l, r);
	int mid = (l + r) / 2;
	upd(v * 2 + 1, l, mid, L, min(mid, R), x);
	upd(v * 2 + 2, mid, r, max(mid, L), R, x);

	t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
}

void upd(int l, int r, int x){
	upd(0, 0, n, l, r, x);
}

long long get(int v, int l, int r, int L, int R){
	if(L >= R) return 1e18;

	push(v, l, r);
	if(l == L && r == R)
		return t[v];

	int mid = (l + r) / 2;
	return min(get(v * 2 + 1, l, mid, L, min(R, mid)), 
		   get(v * 2 + 2, mid, r, max(L, mid), R));		
}

long long get(int l, int r){
	return get(0, 0, n, l, r);
}

int main() {
	scanf("%d", &n);
	for(int i = 0; i < n; ++i){
		scanf("%d", p + i);
        --p[i];
        rp[p[i]] = i;
	}
	for(int i = 0; i < n; ++i)
		scanf("%d", a + i);
	
	b[0] = a[0];
	for(int i = 1; i < n; ++i)
		b[i] = a[i] + b[i - 1];
	build(0, 0, n);
	
	long long res = get(0, n - 1);
	//for(int i = 0; i < n; ++i) cout << get(i, i+1) << ' ';cout << endl;
	for(int i = 0; i < n; ++i){
	    int pos = rp[i];
		upd(pos, n, -a[pos]);
		upd(0, pos, a[pos]);
		res = min(res, get(0, n - 1));
		//for(int i = 0; i < n; ++i) cout << get(i, i+1) << ' ';cout << endl;
	}
	
	cout << res << endl;
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

int add(int x, int y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}

int mul(int x, int y)
{
    return (x * 1ll * y) % MOD;
}

int binpow(int x, int y)
{
    int z = 1;
    while(y)
    {
        if(y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}

int inv(int x)
{
    return binpow(x, MOD - 2);
}

int divide(int x, int y)
{
    return mul(x, inv(y));
}

typedef vector<int> poly;

void norm(poly& p)
{
    while(p.size() > 0 && p.back() == 0)
        p.pop_back();
}

poly operator +(const poly& a, const poly& b)
{
    poly c = a;
    while(c.size() < b.size()) c.push_back(0);
    for(int i = 0; i < b.size(); i++) c[i] = add(c[i], b[i]);
    norm(c);
    return c;
}

poly operator +(const poly& a, int b)
{
    return a + poly(1, b);
}

poly operator +(int a, const poly& b)
{
    return b + a;
}

poly operator *(const poly& a, int b)
{
    poly c = a;                               
    for(int i = 0; i < c.size(); i++) c[i] = mul(c[i], b);
    norm(c);
    return c;
}

poly operator /(const poly& a, int b)
{   
    return a * inv(b);
}

poly operator *(const poly& a, const poly& b)
{
    poly c(a.size() + b.size() - 1);
    for(int i = 0; i < a.size(); i++)
        for(int j = 0; j < b.size(); j++)
            c[i + j] = add(c[i + j], mul(a[i], b[j]));

    norm(c);
    return c;
}

poly interpolate(const vector<int>& x, const vector<int>& y)
{
    int n = int(x.size()) - 1;
    vector<vector<int> > f(n + 1);
    f[0] = y;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= n - i; j++)
            f[i].push_back(divide(add(f[i - 1][j + 1], -f[i - 1][j]), add(x[i + j], -x[j])));
    
    poly cur = poly(1, 1);
    poly res;
    for(int i = 0; i <= n; i++)
    {
        res = res + cur * f[i][0];
        cur = cur * poly({add(0, -x[i]), 1});
    }

    return res;
}

int eval(const poly& a, int x)
{
    int res = 0;
    for(int i = int(a.size()) - 1; i >= 0; i--)
        res = add(mul(res, x), a[i]);
    return res;
}

poly sumFromL(const poly& a, int L, int n)
{
    vector<int> x;
    for(int i = 0; i <= n; i++)
        x.push_back(L + i);
    vector<int> y;
    int cur = 0;
    for(int i = 0; i <= n; i++)
    {
        cur = add(cur, eval(a, x[i]));
        y.push_back(cur);
    }
    return interpolate(x, y);
}

int sumOverSegment(const poly& a, int L, int R)
{
    return eval(sumFromL(a, L, a.size()), R - 1);
}

int main() {
    int n;
    cin >> n;
    vector<int> L(n), R(n);
    for(int i = 0; i < n; i++)
    {
        cin >> L[i] >> R[i];
        R[i]++;
    }
    reverse(L.begin(), L.end());
    reverse(R.begin(), R.end());

    vector<int> coord = {0, MOD - 2};
    for(int i = 0; i < n; i++)
    {
        coord.push_back(L[i]);
        coord.push_back(R[i]);
    }
    sort(coord.begin(), coord.end());
    coord.erase(unique(coord.begin(), coord.end()), coord.end());
    vector<int> cL = coord, cR = coord;
    cL.pop_back();
    cR.erase(cR.begin());
    int cnt = coord.size() - 1;
    vector<poly> cur(cnt);
    for(int i = 0; i < cnt; i++)
        if(cL[i] >= L[0] && cR[i] <= R[0])
            cur[i] = poly(1, inv(R[0] - L[0]));
    for(int i = 1; i < n; i++)
    {
        vector<poly> nxt(cnt);        
        int curSum = 0;
        for(int j = 0; j < cnt; j++)
        {
            nxt[j] = sumFromL(cur[j], cL[j], i) + curSum;
            curSum = add(curSum, sumOverSegment(cur[j], cL[j], cR[j]));    
        }
        for(int j = 0; j < cnt; j++)
            nxt[j] = nxt[j] * (cL[j] >= L[i] && cR[j] <= R[i] ? inv(R[i] - L[i]) : 0);
        cur = nxt;
    }
    int ans = 0;
    for(int i = 0; i < cnt; i++)
        ans = add(ans, sumOverSegment(cur[i], cL[i], cR[i]));

    cout << ans << endl;
}

#include<bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	int tt = clock();
#endif
	
	int T; cin >> T;
	while(T--) {
		int n, d;
		cin >> n >> d;
		
		int x, MAG = (int)sqrt(d) + 10;
		for(x = 0; x < MAG; x++) {
			if(x + (d + x) / (x + 1) <= n)
				break;
		}
		cout << (x < MAG ? "YES" : "NO") << endl;
	}

	return 0;
}

for t in range(int(input())):
	a, b = map(int, input().split())
	print(a * (len(str(b + 1)) - 1))

from math import factorial as fact
mod = 10**9 + 7

def C(n, k):
	return fact(n) // (fact(k) * fact(n - k))

n, m = map(int, input().split())
print(C(n + 2*m - 1, 2*m) % mod)

#include<bits/stdc++.h>

using namespace std;

int n, m;
vector<vector<int> > a;
int a1, a2;

bool can(int mid)
{
    vector<int> msk(1 << m, -1);
    for(int i = 0; i < n; i++)
    {
        int cur = 0;
        for(int j = 0; j < m; j++)
            if(a[i][j] >= mid)
                cur ^= (1 << j);
        msk[cur] = i;
    }
    if(msk[(1 << m) - 1] != -1)
    {
        a1 = a2 = msk[(1 << m) - 1];
        return true;
    }
    for(int i = 0; i < (1 << m); i++)
        for(int j = 0; j < (1 << m); j++)
            if(msk[i] != -1 && msk[j] != -1 && (i | j) == (1 << m) - 1)
            {
                a1 = msk[i];
                a2 = msk[j];
                return true;
            }
    return false;
}

int main()
{
    scanf("%d %d", &n, &m);
    a.resize(n, vector<int>(m));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            scanf("%d", &a[i][j]);
    int lf = 0;
    int rg = int(1e9) + 43;
    while(rg - lf > 1)
    {
        int m = (lf + rg) / 2;
        if(can(m))
            lf = m;
        else
            rg = m;            
    }
    assert(can(lf));
    printf("%d %d\n", a1 + 1, a2 + 1);
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)
#define x first 
#define y second

using namespace std;

const int N = 300 * 1000 + 13;
const int P = 550;

typedef pair<int, int> pt;

int n;
int a[N];
vector<int> pos[N];
pt ans[N];

int cnt[N];
int tot;

void add(int x){
	++cnt[x];
	if (cnt[x] == 1) ++tot;
}

void rem(int x){
	if (cnt[x] == 1) --tot;
	--cnt[x];
}

int f[N];

void upd(int x){
	for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
		++f[i];
}

int get(int x){
	int res = 0;
	for (int i = x; i < N; i |= i + 1)
		res += f[i];
	return res;
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	forn(i, m){
		scanf("%d", &a[i]);
		--a[i];
	}
	forn(i, m){
		pos[a[i]].push_back(i);
	}
	
	vector<pt> qr;
	forn(i, n){
		for (int j = 1; j < int(pos[i].size()); ++j)
			qr.push_back(make_pair(pos[i][j - 1] + 1, pos[i][j] - 1));
		if (!pos[i].empty())
			qr.push_back(make_pair(pos[i].back() + 1, m - 1));
	}
	
	sort(qr.begin(), qr.end(), [](const pt &a, const pt &b){
		if (a.x / P != b.x / P)
			return a.x < b.x;
		if ((a.x / P) & 1)
			return a.y < b.y;
		return a.y > b.y;
	});
	
	forn(i, n) ans[i] = {i, i};
	forn(i, m) ans[a[i]].x = 0;
	
	int L = 0, R = -1;
	forn(i, qr.size()){
		int l = qr[i].x;
		int r = qr[i].y;
		if (r < l) continue;
		
		int x = a[qr[i].x - 1];
		while (L < l) rem(a[L++]);
		while (L > l) add(a[--L]);
		while (R > r) rem(a[R--]);
		while (R < r) add(a[++R]);
		
		ans[x].y = max(ans[x].y, tot);
	}
	forn(i, m){
		if (i == pos[a[i]][0]){
			ans[a[i]].y = max(ans[a[i]].y, a[i] + get(a[i]));
			upd(a[i]);
		}
	}
	forn(i, n) if (pos[i].empty()){
		ans[i].y = max(ans[i].y, i + get(i));
	}
	
	forn(i, n) printf("%d %d\n", ans[i].x + 1, ans[i].y + 1);
	return 0;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)
#define x first 
#define y second

using namespace std;

const int N = 300 * 1000 + 13;

typedef pair<int, int> pt;

int n;
int a[N];
vector<int> pos[N];
pt ans[N];
int prv[N];

vector<int> t[4 * N];

void build(int v, int l, int r){
	if (l == r - 1){
		t[v].push_back(prv[l]);
		return;
	}
	int m = (l + r) / 2;
	build(v * 2, l, m);
	build(v * 2 + 1, m, r);
	t[v].resize(r - l);
	merge(t[v * 2].begin(), t[v * 2].end(), t[v * 2 + 1].begin(), t[v * 2 + 1].end(), t[v].begin());
}

int get(int v, int l, int r, int L, int R, int val){
	if (L >= R)
		return 0;
	if (l == L && r == R)
		return lower_bound(t[v].begin(), t[v].end(), val) - t[v].begin();
	int m = (l + r) / 2;
	return get(v * 2, l, m, L, min(m, R), val) + get(v * 2 + 1, m, r, max(m, L), R, val);
}

int f[N];

void upd(int x){
	for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
		++f[i];
}

int get(int x){
	int res = 0;
	for (int i = x; i < N; i |= i + 1)
		res += f[i];
	return res;
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	forn(i, m){
		scanf("%d", &a[i]);
		--a[i];
	}
	forn(i, m){
		pos[a[i]].push_back(i);
	}
	
	vector<pt> qr;
	forn(i, n){
		for (int j = 1; j < int(pos[i].size()); ++j)
			qr.push_back(make_pair(pos[i][j - 1] + 1, pos[i][j] - 1));
		if (!pos[i].empty())
			qr.push_back(make_pair(pos[i].back() + 1, m - 1));
	}
	
	forn(i, n) ans[i] = {i, i};
	forn(i, m) ans[a[i]].x = 0;
	
	forn(i, n){
		int cur = -1;
		for (auto it : pos[i]){
			prv[it] = cur;
			cur = it;
		}
	}
	build(1, 0, m);
	
	forn(i, qr.size()){
		int l = qr[i].x;
		int r = qr[i].y;
		if (r < l) continue;
		int x = a[qr[i].x - 1];
		int cnt = get(1, 0, m, l, r + 1, l);
		ans[x].y = max(ans[x].y, cnt);
	}
	
	forn(i, m){
		if (i == pos[a[i]][0]){
			ans[a[i]].y = max(ans[a[i]].y, a[i] + get(a[i]));
			upd(a[i]);
		}
	}
	forn(i, n) if (pos[i].empty()){
		ans[i].y = max(ans[i].y, i + get(i));
	}
	
	forn(i, n) printf("%d %d\n", ans[i].x + 1, ans[i].y + 1);
	return 0;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int N = 600 * 1000 + 13;

int f[N];

void upd(int x, int val){
	for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
		f[i] += val;
}

int get(int x){
	int res = 0;
	for (int i = x; i < N; i |= i + 1)
		res += f[i];
	return res;
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	vector<int> mn(n);
	iota(mn.begin(), mn.end(), 0);
	vector<int> mx = mn;
	
	vector<int> a(m);
	forn(i, m){
		scanf("%d", &a[i]);
		--a[i];
		mn[a[i]] = 0;
	}
	
	vector<int> pos(n);
	forn(i, n) pos[i] = n - i - 1;
	forn(i, n) upd(i, 1);
	
	forn(i, m){
		mx[a[i]] = max(mx[a[i]], get(pos[a[i]] + 1));
		upd(pos[a[i]], -1);
		pos[a[i]] = i + n;
		upd(pos[a[i]], 1);
	}
	forn(i, n){
		mx[i] = max(mx[i], get(pos[i] + 1));
	}
	
	forn(i, n) printf("%d %d\n", mn[i] + 1, mx[i] + 1);
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 443;

int n1, n2, m, r, b;
string s1, s2;
int u[N];
int v[N];

struct edge
{
    int y, c, f, cost;
    edge() {};
    edge(int y, int c, int f, int cost) : y(y), c(c), f(f), cost(cost) {};
};

int bal[N][N];
int s, t, oldS, oldT, V;
vector<int> g[N];
vector<edge> e;

void add(int x, int y, int c, int cost)
{
    g[x].push_back(e.size());
    e.push_back(edge(y, c, 0, cost));
    g[y].push_back(e.size());
    e.push_back(edge(x, 0, 0, -cost));
}

int rem(int num)
{
    return e[num].c - e[num].f;
}   

void add_LR(int x, int y, int l, int r, int cost)
{
    int c = r - l;
    if(l > 0)
    {
        add(s, y, l, cost);
        add(x, t, l, cost);
    }
    if(c > 0)
    {
        add(x, y, c, cost);
    }
}

int p[N];
int d[N];
int pe[N];
int inq[N];

bool enlarge()
{
    for(int i = 0; i < V; i++)
    {
        d[i] = int(1e9);
        p[i] = -1;
        pe[i] = -1;
        inq[i] = 0;
    }
    d[s] = 0;
    queue<int> q;
    q.push(s);
    inq[s] = 1;
    while(!q.empty())
    {
        int k = q.front();
        q.pop();
        inq[k] = 0;
        for(auto z : g[k])
        {
            if(!rem(z)) continue;
            if(d[e[z].y] > d[k] + e[z].cost)
            {
                p[e[z].y] = k;
                pe[e[z].y] = z;
                d[e[z].y] = d[k] + e[z].cost;
                if(!inq[e[z].y])
                {
                    q.push(e[z].y);
                    inq[e[z].y] = 1;
                }
            }
        }
    }
    if(p[t] == -1)
        return false;
    int cur = t;
    while(cur != s)
    {
        e[pe[cur]].f++;
        e[pe[cur] ^ 1].f--;
        cur = p[cur];
    }
    return true;
}

void add_edge(int x, int y)
{
    add(x, y + n1, 1, r);
    add(y + n1, x, 1, b);
}

void impose_left(int x)
{
    if(s1[x] == 'R')
    {
        add_LR(oldS, x, 1, m, 0);
    }
    else if(s1[x] == 'B')
    {
        add_LR(x, oldT, 1, m, 0);
    }
    else
    {
        add(oldS, x, m, 0);
        add(x, oldT, m, 0);
    }
}

void impose_right(int x)
{
    if(s2[x] == 'R')
    {
        add_LR(x + n1, oldT, 1, m, 0);
    }
    else if(s2[x] == 'B')
    {
        add_LR(oldS, x + n1, 1, m, 0);
    }
    else
    {
        add(oldS, x + n1, m, 0);
        add(x + n1, oldT, m, 0);
    }
}

void construct_bal()
{
    for(int i = 0; i < n1; i++)
    {
        for(auto z : g[i])
        {
            if(e[z].y >= n1 && e[z].y < n1 + n2)
                bal[i][e[z].y - n1] += e[z].f;
        }
    }
}

void find_ans()
{
    int res = 0;
    string w = "";
    for(auto x : g[s])
        if(rem(x))
        {
            cout << -1 << endl;
            return;
        }
    for(int i = 0; i < m; i++)
    {
        if(bal[u[i]][v[i]] > 0)
        {
            bal[u[i]][v[i]]--;
            res += r;
            w += "R";
        }
        else if(bal[u[i]][v[i]] < 0)
        {
            bal[u[i]][v[i]]++;
            res += b;
            w += "B";
        }
        else w += "U";
    }
    cout << res << endl << w << endl;
}

int main()
{                       
    cin >> n1 >> n2 >> m >> r >> b;
    cin >> s1;
    cin >> s2;
    for(int i = 0; i < m; i++)
    {
        cin >> u[i] >> v[i];
        u[i]--;
        v[i]--;
    }

    oldS = n1 + n2;
    oldT = oldS + 1;
    s = oldT + 1;
    t = s + 1;
    V = t + 1;

    for(int i = 0; i < n1; i++)
        impose_left(i);
    for(int i = 0; i < n2; i++)
        impose_right(i);
    for(int i = 0; i < m; i++)
        add_edge(u[i], v[i]);
    add(oldT, oldS, 100000, 0);
    while(enlarge());
    construct_bal();
    find_ans();
}

for t in range(int(input())):
	a = sorted(list(map(int, input().split())))
	print('Yes' if a[2] <= a[0] + a[1] + 1 else 'No')

for t in range(int(input())):
    n, t = map(int, input().split())
    a = list(map(int, input().split()))
    id = 0
    for i in range(n):
        if a[i] > a[id]:
            id = i
        t -= a[i]
        if t < 0:
            break

    if t >= 0:
        id = -1 
    print(id + 1)

for t in range(int(input())):
	n, m = map(int, input().split())
	a = [x - 1 for x in list(map(int, input().split()))]
	b = [x - 1 for x in list(map(int, input().split()))]
	pos = a[:]
	for i in range(n):
		pos[a[i]] = i
	
	lst = -1
	res = m
	for i in range(m):
		if pos[b[i]] > lst:
			res += 2 * (pos[b[i]] - i)
			lst = pos[b[i]]
	
	print(res)

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define pb push_back
#define mp make_pair
#define sqr(a) ((a) * (a))
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)

const int MOD = 998244353;
const int N = 1e6 + 7;

int n;
vector<int> a[N];
int cnt[N];
int inv[N];

int add(int a, int b) {
	a += b;
	if (a >= MOD) a -= MOD;
	return a;
}

int mul(int a, int b) {
	return a * 1ll * b % MOD;
}

int binpow(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}

int main() {
	scanf("%d", &n);
	forn(i, n) {
		int k;
		scanf("%d", &k);
		a[i].resize(k);
		forn(j, k) scanf("%d", &a[i][j]);
		forn(j, k) cnt[a[i][j]]++;
	}
	
	forn(i, N) inv[i] = binpow(i, MOD - 2);
	
	int ans = 0;
	forn(i, n) for (auto x : a[i])
		ans = add(ans, mul(mul(inv[n], inv[sz(a[i])]), mul(cnt[x], inv[n])));
			
	printf("%d\n", ans);
}

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define pb push_back
#define mp make_pair
#define sqr(a) ((a) * (a))
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i < int(r); ++i)

typedef long long li;
typedef long double ld;

const int N = 55;
const li INF = 2e18;

int n;
li k;

li cycl[N], cnt[N];
bool used[N];
int ans[N];

li add(li x, li y) {
	return min(INF, x + y);
}

li mul(li x, li y) {
	ld t = ld(x) + y;
	if (t > INF) return INF;
	return x * y;
}

void solve() {
	cin >> n >> k;
	--k;

	cycl[0] = cycl[1] = 1;
	fore(i, 2, n + 1) 
		cycl[i] = mul(cycl[i - 1], i - 1);
		
	cnt[n] = 1;
	for (int i = n - 1; i >= 0; i--) {
		cnt[i] = 0;
		fore(val, i, n) {
			int len = (val - i) + 1;
			cnt[i] = add(cnt[i], mul(cnt[i + len], cycl[len - 1]));
		}
	}
	
	if (cnt[0] <= k) {
		cout << -1 << endl;
		return;
	}
	
	memset(used, 0, sizeof(used));
	memset(ans, -1, sizeof(ans));
	
	forn(i, n) {
		fore(val, i, n) {
			int len = (val - i) + 1;
			li cur = mul(cnt[i + len], cycl[len - 1]); 
			
			if (cur <= k)  {
				k -= cur;
				continue;	
			}
			
			ans[i] = val;
			used[val] = true;
			
			for (int j = i + 1; j < i + len; j++) {
				int lft = len - (j - i) - 1;
				fore(nval, i, val) if (!used[nval] && j != nval) {
					if (j != i + len - 1) {
						int tmp = ans[nval];
						while (tmp != -1 && tmp != j) 
							tmp = ans[tmp];
						if (tmp == j) continue;
					}
					
					li cur = mul(cnt[i + len], cycl[lft]); 
					if (cur <= k) {
						k -= cur;
						continue;	
					}
					
					ans[j] = nval;
					used[nval] = true;		
					break;
				}
			}
				
			i += len - 1;
			break;
		}
	}

	forn(i, n) cout << ans[i] + 1 << ' ';
	cout << endl;
}

int main() {
	int tc;
	cin >> tc;
	forn(i, tc) solve();
}

#include <bits/stdc++.h>

using namespace std;

const int N = 1000 * 1000 + 11;
const int INF = 1e9;

int n, k, l;
string s;
int a[N];
pair<int, int> dp[N];

int calc(int mid) {
	for (int i = 0; i <= n; ++i) {
		dp[i] = make_pair(INF, INF);
	}
	dp[0] = make_pair(0, 0);
	for (int i = 0; i < n; ++i) {
		if (dp[i + 1] > make_pair(dp[i].first + a[i], dp[i].second)) {
			dp[i + 1] = make_pair(dp[i].first + a[i], dp[i].second);
		}
		if (dp[min(n, i + l)] > make_pair(dp[i].first + mid, dp[i].second + 1)) {
			dp[min(n, i + l)] = make_pair(dp[i].first + mid, dp[i].second + 1);
		}
	}
	return dp[n].second;
}

int solve() {
	int l = 0, r = n;
	int res = 0;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (calc(mid) > k) {
			l = mid + 1;
			res = mid;
		} else {
			r = mid - 1;
		}
	}
	if (calc(res) <= k) return 0;
	calc(res + 1);
	return dp[n].first - (res + 1) * 1ll * k;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> k >> l >> s;
	for (int i = 0; i < n; ++i) {
		a[i] = islower(s[i]) > 0;
	}
	int ans = INF;
	ans = min(ans, solve());
	for (int i = 0; i < n; ++i) {
		a[i] = isupper(s[i]) > 0;
	}
	ans = min(ans, solve());
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

string p, h;

bool read(){
	if (!(cin >> p >> h))
		return false;
	return true;
}

void solve(){
	int n = h.size();
	vector<int> cntp(26);
	forn(i, p.size())
		++cntp[p[i] - 'a'];
	forn(i, n){
		vector<int> cnth(26);
		for (int j = i; j < n; ++j){
			++cnth[h[j] - 'a'];
			if (cntp == cnth){
				puts("YES");
				return;
			}
		}
	}
	puts("NO");
}

int main() {
	int tc;
	scanf("%d", &tc);
	forn(_, tc){
		read();
		solve();
	}
	return 0;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int AL = 26;
string p, h;

bool read(){
	if (!(cin >> p >> h))
		return false;
	return true;
}

void solve(){
	vector<int> cntp(AL), cnt(AL);
	vector<bool> eq(AL);
	int sum = 0;
	
	auto chg = [&cntp, &cnt, &eq, &sum](int c, int val){
		sum -= eq[c];
		cnt[c] += val;
		eq[c] = (cntp[c] == cnt[c]);
		sum += eq[c];
	};
	
	forn(i, p.size())
		++cntp[p[i] - 'a'];
	forn(i, AL){
		eq[i] = (cnt[i] == cntp[i]);
		sum += eq[i];
	}
	
	int m = p.size();
	int n = h.size();
	forn(i, n){
		chg(h[i] - 'a', 1);
		if (i >= m) chg(h[i - m] - 'a', -1);
		if (sum == AL){
			puts("YES");
			return;
		}
	}
	
	puts("NO");
}

int main() {
	int tc;
	scanf("%d", &tc);
	forn(_, tc){
		read();
		solve();
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int t, a, b;

bool ok(int res, int d){
	long long sum = res * 1LL * (res + 1) / 2;
	if(sum < d) return false;
	return sum % 2 == d % 2;
}	

int main() {		
	cin >> t;
	for(int tc = 0; tc < t; ++tc){
		cin >> a >> b;
		int d = abs(a - b);
		if(d == 0){ 
			cout << "0\n";
			continue;
		}

		int res = 1;
		while(!ok(res, d)) ++res;
		cout << res << endl;
		
	}
	return 0;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

int n;
vector<int> a;

bool read(){
	if (scanf("%d", &n) != 1)
		return false;
	a.resize(2 * n);
	forn(i, 2 * n)
		scanf("%d", &a[i]);
	return true;
}

void solve(){
	int cur = 0;
	map<int, int> difr;
	
	difr[0] = 0;
	cur = 0;
	for (int i = n; i < 2 * n; ++i){
		if (a[i] == 1)
			++cur;
		else
			--cur;
		if (!difr.count(cur))
			difr[cur] = i - (n - 1);
	}
	
	int ans = 2 * n;
	int dif = count(a.begin(), a.end(), 1) - count(a.begin(), a.end(), 2);
	
	cur = 0;
	for (int i = n - 1; i >= 0; --i){
		if (a[i] == 1)
			++cur;
		else
			--cur;
		if (difr.count(dif - cur))
			ans = min(ans, n - i + difr[dif - cur]);
	}
	if (difr.count(dif)){
		ans = min(ans, difr[dif]);
	}
	
	printf("%d\n", ans);
}

int main() {
	int tc;
	scanf("%d", &tc);
	forn(_, tc){
		read();
		solve();
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); i++)

typedef long long li;
typedef pair<li, li> pt;

const int N = 500010;

int n;
pt a[N];
vector<int> g[N];
bool used[N];

void dfs(int v, int p = -1) {
	used[v] = true;
	for (auto to : g[v]) if (to != p) {
		if (!used[to])
			dfs(to, v);
	}
}

int main() {
	scanf("%d", &n);
	forn(i, n) scanf("%d%d", &a[i].x, &a[i].y);
	
	vector<pt> evs;
	forn(i, n) {
		evs.pb(mp(a[i].x, i));
		evs.pb(mp(a[i].y, i));
	}
	
	sort(all(evs));
	
	int cnt = 0;
	set<pt> cur;
	for (auto it : evs) {
		if (cnt >= n) break;
		if (cur.count(it)) {
			cur.erase(it);
		} else {
			int i = it.y;
			int r = a[i].y;
			for (auto jt : cur) {
				if (jt.x > r) break;
				int j = jt.y;
				g[i].pb(j);
				g[j].pb(i);
				cnt++;
				if (cnt >= n) break;
			}
			cur.insert(mp(a[i].y, i));
		}
	}
	
	dfs(0);
	puts(cnt == n - 1 && count(used, used + n, 1) == n ? "YES" : "NO");
}

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(), (a).end()
#define sz(a) int((a).size())
#define forn(i, n) for (int i = 0; i < int(n); i++)

typedef pair<int, int> pt;

const int N = 500 * 1000 + 13;

int n;
vector<int> g[N], vs[N];
pt segs[N];

void dfs(int v, int p = -1) {
	int sum = 0;
	int bst = -1;
	for (auto to : g[v]) if (to != p) {
		dfs(to, v);
		sum += 2 * sz(vs[to]);
		if (bst == -1 || sz(vs[to]) > sz(vs[bst]))
			bst = to;
	}
	
	if (bst == -1) {
		vs[v].pb(v);
		segs[v] = mp(1, 2);
		return;
	}
	
	swap(vs[v], vs[bst]);
	int lst = segs[bst].y;
	
	sum -= 2 * sz(vs[v]);
	sum += 1;
	segs[bst].y += sum;
	
	for (auto to : g[v]) if (to != p && to != bst) {
		int add = lst - 1;
		for (auto u : vs[to]) {
			segs[u].x += add;
			segs[u].y += add;
			vs[v].pb(u);
		}
		lst = segs[to].y;
		sum -= 2 * sz(vs[to]);
		segs[to].y += sum;
		vs[to].clear();
	}
	
	vs[v].pb(v);
	segs[v] = mp(lst, segs[bst].y + 1);
}	

int main() {
	scanf("%d", &n);
	forn(i, n - 1) {
		int x, y;
		scanf("%d%d", &x, &y);
		--x; --y;
		g[x].pb(y);
		g[y].pb(x);
	}
	
	dfs(0);
	
	for (int i = 0; i < n; i++)
		printf("%d %d\n", segs[i].x, segs[i].y);
	
	return 0;
}

1278F - Cards

First of all, I would like to thank Errichto for his awesome lecture on expected value: part 1, part 2. This problem was invented after I learned the concept of estimating the square of expected value from that lecture — and the editorial uses some ideas that were introduced there.

Okay, now for the editorial itself. We call a number $$$a$$$ as good if $$$1 \le a \le n$$$, and the $$$a$$$-th shuffle of the deck resulted in a joker on top. $$$x$$$ from our problem is the number of such good numbers $$$a$$$. We can represent $$$x^2$$$ as the number of pairs $$$(a_1, a_2)$$$ such that every element of the pair is a good number, $$$x^3$$$ as the number of triples, and so on — $$$x^k$$$ is the number of $$$k$$$-tuples $$$(a_1, a_2, \dots, a_k)$$$ such that each element of a tuple is a good number.

So we can rewrite the expected value of $$$x^k$$$ as the expected number of such tuples, or the sum of $$$P(t)$$$ over all tuples $$$t$$$, where $$$P(t)$$$ is the probability that $$$t$$$ consists of good numbers. How to calculate the probability that $$$t$$$ is a good tuple? Since all shuffles of the deck result in a joker with probability $$$\frac{1}{m}$$$, $$$P(t)$$$ should be equal to $$$\frac{1}{m^k}$$$ — but that is true only if all elements in $$$t$$$ are unique. How to deal with tuples with repeating elements? Since all occurences of the same element are either good or bad (with probability $$$\frac{1}{m}$$$ of being good), the correct formula for $$$P(t)$$$ is $$$P(t) = \frac{1}{m^d}$$$, where $$$d$$$ is the number of distinct elements in the tuple.

Okay, then for each $$$d \in [1, k]$$$ we have to calculate the number of $$$k$$$-tuples with exactly $$$d$$$ distinct elements. To do that, we use dynamic programming: let $$$dp_{i, j}$$$ be the number of $$$i$$$-tuples with exactly $$$j$$$ distinct elements. Each transition in this dynamic programming solution models adding an element to the tuple; if we want to compute the transitions leading from $$$dp_{i, j}$$$, we either add a new element to the tuple (there are $$$n - j$$$ ways to choose it, and we enter the state $$$dp_{i + 1, j + 1}$$$), or we add an already existing element (there are $$$j$$$ ways to choose it, and we enter the state $$$dp_{i + 1, j}$$$).

Overall complexity is $$$O(k^2 \log MOD)$$$ or $$$O(k^2 + \log MOD)$$$, depending on your implementation.

#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;
const int N = 5043;

int add(int x, int y)
{
	x += y;
	while(x >= MOD) x -= MOD;
	while(x < 0) x += MOD;
	return x;
}

int mul(int x, int y)
{
	return (x * 1ll * y) % MOD;
}

int binpow(int x, int y)
{
	int z = 1;
	while(y > 0)
	{
		if(y % 2 == 1)
			z = mul(z, x);
		x = mul(x, x);
		y /= 2;
	}
	return z;
}

int inv(int x)
{
	return binpow(x, MOD - 2);
}

int n, m, k;

int dp[N][N];

int main()
{
	cin >> n >> m >> k;
	dp[0][0] = 1;
	for(int i = 0; i < k; i++)
		for(int j = 0; j < k; j++)
		{
			dp[i + 1][j] = add(dp[i + 1][j], mul(dp[i][j], j));
			dp[i + 1][j + 1] = add(dp[i + 1][j + 1], mul(dp[i][j], n - j));
		}
	int ans = 0;
	for(int i = 1; i <= k; i++)
		ans = add(ans, mul(dp[k][i], binpow(inv(m), i)));
	cout << ans << endl;
}

#include<bits/stdc++.h>
using namespace std;

int c, sum;

inline bool read() {
	if(!(cin >> c >> sum))
		return false;
	return true;
}

inline void solve() {
	int d = sum / c;
	int rem = sum % c;
	cout << rem * (d + 1) * (d + 1) + (c - rem) * d * d << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif
	int n; cin >> n;
	while(n--) {
		read();
		solve();
	}
	return 0;
}

for t in range(int(input())):
	a, b = map(int, input().split())
	if a > b:
		a, b = b, a
	print ('YES' if ( ((a + b) % 3) == 0 and a * 2 >= b) else 'NO')

#include<bits/stdc++.h>
using namespace std;
typedef long long li;

li a, b, k;

inline bool read() {
	if(!(cin >> a >> b >> k))
		return false;
	return true;
}

inline void solve() {
	li g = __gcd(a, b);
	a /= g;
	b /= g;
	if(a > b)
		swap(a, b);
	if((k - 1) * a + 1 < b)
		cout << "REBEL";
	else
		cout << "OBEY";
	cout << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif
	int tc; cin >> tc;
	while(tc--) {
		read();
		solve();
	}
	return 0;
}

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<map>

using namespace std;

typedef pair<int, int> pt;

#define x first
#define y second


int m, n, k, t;
vector<int> l, r, d, a;

bool can(int x)
{
	int mn = int(1e9);
	for (int i = 0; i < x; i++)
		mn = min(mn, a[i]);
	vector<pt> segm;
	for (int i = 0; i < k; i++)
		if (d[i] > mn)
			segm.push_back(make_pair(l[i], r[i]));
	int req_time = 0;
	sort(segm.begin(), segm.end());
	int lastr = 0;
	for (auto s : segm)
	{
		if (s.x <= lastr)
		{
			req_time += max(0, s.y - lastr);
			lastr = max(s.y, lastr);
		}
		else
		{
			req_time += s.y - s.x + 1;
			lastr = s.y;
		}
	}
	req_time = 2 * req_time + n + 1;
	return req_time <= t;
}

int main()
{
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	scanf("%d %d %d %d", &m, &n, &k, &t);
	a.resize(m);
	for (int i = 0; i < m; i++)
		scanf("%d", &a[i]);
	sort(a.begin(), a.end());
	reverse(a.begin(), a.end());
	l.resize(k);
	r.resize(k);
	d.resize(k);
	for (int i = 0; i < k; i++)
		scanf("%d %d %d", &l[i], &r[i], &d[i]);

	int lf = 0;
	int rg = m + 1;
	while (rg - lf > 1)
	{
		int mid = (lf + rg) / 2;
		if (can(mid))
			lf = mid;
		else
			rg = mid;
	}
	printf("%d\n", lf);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int LOGN = 20;
const int N = (1 << LOGN) + 99;
const long long INF = 1e18;

int n;
int a[N];
long long dp[LOGN+2][N];
int sum[100];

long long calc(int cnt, int pos){
	long long &res = dp[cnt][pos];
	if(res != -1) return res;

	if(a[pos] == -1) return res = 0;
	int rem = sum[cnt] - pos;

	res = INF;
	if(cnt < LOGN)
		res = calc(cnt + 1, pos + 1) + a[pos];
	if(rem > 0)		
		res = min(res, calc(cnt, pos + 1));

	return res;
}

int main() {	
	scanf("%d", &n);
	for(int i = 0; i < n; ++i)
		scanf("%d", a + i);

	for(int i = 1, x = n / 2; i < 100; ++i, x /= 2)
		sum[i] = sum[i - 1] + x;
	
	reverse(a, a + n);
	memset(dp, -1, sizeof dp);
	printf("%lld", calc(0, 0));	
	return 0;
}                             	

#include<bits/stdc++.h>
using namespace std;
int n ;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7 ;
vector<int> E[maxn];
vector<int> in[maxn] , out[maxn];
int cm = 0;
int l[maxn] , dfn = 0 , dep[maxn];
int g[maxn];
int siz[maxn] , top[maxn] , h[maxn] , f[maxn];
///-----segment tree
struct seg
{
    int l , r;
    int sum , add ;
}Node[maxn * 4];

void build(int u,int l,int r)
{
    Node[u].l = l , Node[u].r = r;
    Node[u].sum = Node[u].add = 0;
    if(l == r) return ;
    build(u<<1 , l , (l + r >> 1));
    build(u<<1|1 , (l + r >>1) + 1 , r);
    return ;
}
void pd(int u)
{
    Node[u].sum = (1LL*Node[u].add*(Node[u].r - Node[u].l + 1) + Node[u].sum) % mod ;
    if(Node[u].l == Node[u].r) {
        Node[u].add = 0 ;return ;
    }
    (Node[u<<1].add += Node[u].add ) %= mod;
    (Node[u<<1|1].add += Node[u].add ) %= mod;
    Node[u].add = 0 ; return ;
}
void modify(int u,int l,int r,int v)
{
    if(Node[u].l == l && Node[u].r == r) {
        (Node[u].add += v ) %= mod;
        pd(u) ; return ;
        return ;
    }
    pd(u) ;
    if(Node[u<<1].r >= r) {modify(u<<1 , l , r , v) ; pd(u<<1|1);}
    else if(Node[u<<1|1].l <= l) {modify(u<<1|1 , l , r , v) ; pd(u<<1) ;}
    else {
        modify(u<<1 , l , Node[u<<1].r , v) ;
        modify(u<<1|1 , Node[u<<1|1].l , r , v);
    }
    Node[u].sum = (Node[u<<1].sum + Node[u<<1|1].sum) % mod;
    return ;
}
int query(int u,int l,int r)
{
    pd(u) ;
    if(Node[u].l == l && Node[u].r == r) return Node[u].sum ;
    if(Node[u<<1].r >= r) return query(u<<1 , l , r) ;
    else if(Node[u<<1|1].l <= l) return query(u<<1|1 , l , r);
    else return (query(u<<1 , l , Node[u<<1].r) + query(u<<1|1 , Node[u<<1|1].l , r)) % mod;
}
///---segment tree end
void dfs(int fa,int u,int d)
{
    f[u] = fa;
    dep[u] = d;siz[u] = 1;h[u] = -1;
    for(int i = 0;i < E[u].size();i++) {
        if(E[u][i] != fa) {
            dfs(u , E[u][i] , d + 1) ;siz[u] += siz[E[u][i]];
            if(h[u] == -1 || siz[E[u][i]] > siz[E[u][h[u]]]) h[u] = i;
        }
    }
    return ;
}
void dfs2(int fa,int u)
{
    l[u] = ++dfn;
    if(h[u] != -1) {
        top[E[u][h[u]]] = top[u] ;
        dfs2(u , E[u][h[u]]);
    }
    for(int i = 0;i < E[u].size();i++) {
        if(E[u][i] != fa && i != h[u]) {
            top[E[u][i]] = E[u][i] ;
            dfs2(u , E[u][i]) ;
        }
    }
    return ;
}
int fpow(int a,int b)
{
    int ans = 1;
    while(b) {
        if(b & 1) ans = (1LL * ans * a) % mod;
        a = (1LL * a * a) % mod ;b >>= 1;
    }
    return ans;
}
void add(int u,int v)
{
    while(u) {
        modify(1 , l[top[u]] , l[u] , v) ;
        u = f[top[u]] ;
    }
    return ;
}
int cal(int u)
{
    int ans = mod - query(1 , 1 , 1);
    while(u) {
        ans = (ans + query(1 , l[top[u]] , l[u])) % mod;
        u = f[top[u]] ;
    }
    return ans;
}
int main()
{
    scanf("%d",&n) ;
    int P = 1;
    for(int i = 1;i <= n;i++) {
        int l , r;scanf("%d%d",&l,&r) ;
        in[l].push_back(i) ;
        out[r + 1].push_back(i) ; cm = max(cm , r);
        g[i] = fpow(r - l + 1 , mod - 2) ;
        P = 1LL * P * (r - l + 1) % mod;
    }
    for(int i = 1;i < n;i++) {
        int u , v;scanf("%d%d",&u,&v) ;
        E[u].push_back(v) ; E[v].push_back(u) ;
    }
    dfs(0 , 1 , 0) ; top[1] = 1;
    dfs2(0 , 1) ;
    build(1 , 1 , n) ;
    int ans = 0 , cur = 0;
    int d1 = 0 , d2 = 0 , u , d3 = 0;
    for(int i = 1;i <= cm;i++) {
        for(int j = 0;j < out[i].size();j++) {
            u = out[i][j] ;
            d1 = (d1 - 1LL * dep[u] * g[u] % mod + mod) % mod;
            d2 = (d2 - g[u] + mod) % mod ;
            d3 = (d3 - 1LL*dep[u]*g[u] % mod * g[u] % mod + mod) % mod;
            add(u , mod - g[u]) ;
            cur = (cur - 1LL * g[u] * cal(u) % mod + mod) % mod;
        }
        for(int j = 0;j < in[i].size();j++) {
            u = in[i][j] ;
            d1 = (d1 + 1LL * dep[u] * g[u]) % mod;
            d2 = (d2 + g[u]) % mod;
            d3 = (d3 + 1LL*dep[u]*g[u]%mod*g[u]) % mod;
            cur = (cur + 1LL * g[u] * cal(u)) % mod;
            add(u , g[u]) ;
        }
        ans = (ans + 1LL * d1 * d2%mod - 2LL*cur - d3) % mod;
        ans = (ans + mod) % mod;
    }
    ans = 1LL * ans * P % mod;
    printf("%d\n",ans);
    return 0;
}

import kotlin.math.abs
fun main() {
    val q = readLine()!!.toInt()
    for (ct in 1..q) {
        val (n, x, a, b) = readLine()!!.split(' ').map { it.toInt() }
        println(minOf(n - 1, abs(a - b) + x))
    }
}

#include <bits/stdc++.h>

using namespace std;

void solve() {
	int x, y;
	cin >> x >> y;
	
	if (x > 3) puts("YES");
	else if (x == 1) puts(y == 1 ? "YES" : "NO");
	else puts(y <= 3 ? "YES" : "NO");
}

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

#include<bits/stdc++.h>
using namespace std;

#define sz(a) int((a).size())

int n;
vector<int> a;

inline bool read() {
	if(!(cin >> n))
		return false;
	a.resize(n);
	for(int i = 0; i < n; i++)
		cin >> a[i];
	return true;
}

inline void solve() {
	int ans = n + 5;
	vector<int> lst(n + 1, -1);
	for(int i = 0; i < n; i++) {
		if(lst[a[i]] != -1)
			ans = min(ans, i - lst[a[i]] + 1);
		lst[a[i]] = i;
	}
	if(ans > n)
		ans = -1;
	cout << ans << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	int tc; cin >> tc;
	while(tc--) {
		assert(read());
		solve();
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = int(2e5) + 99;

int t;
int n;
int a[N];
int m;
int p[N], s[N];
int bst[N];

int main() {	
	scanf("%d", &t);
	for(int tc = 0; tc < t; ++tc){
		scanf("%d", &n);
		for(int i = 0; i <= n; ++i) bst[i] = 0;
		for(int i = 0; i < n; ++i)
			scanf("%d", a + i);
		scanf("%d", &m);
		for(int i = 0; i < m; ++i){
			scanf("%d %d", p + i, s + i);
			bst[s[i]] = max(bst[s[i]], p[i]);
		}
		for(int i = n - 1; i >= 0; --i)
			bst[i] = max(bst[i], bst[i + 1]);	
		

		int pos = 0;
		int res = 0;
		bool ok = true;
		while(pos < n){
			++res;
			int npos = pos;
			int mx = 0;
			while(true){
				mx = max(mx, a[npos]);
				if(mx > bst[npos - pos + 1]) break;
				++npos;
			}
	
			if(pos == npos){
				ok = false;
				break;
			}
			pos = npos;
		}

		if(!ok) res = -1;
		printf("%d\n", res);
	}

	return 0;
}                             	            	

#include <bits/stdc++.h>

using namespace std;

int main() 
{
	int k1, k2, k3;
	scanf("%d %d %d", &k1, &k2, &k3);
	int n = k1 + k2 + k3;
	vector<int> a(n);
	for(int i = 0; i < k1; i++)
	{
		int x;
		scanf("%d", &x);
		a[x - 1] = 0;
	}
	for(int i = 0; i < k2; i++)
	{
		int x;
		scanf("%d", &x);
		a[x - 1] = 1;
	}
	for(int i = 0; i < k3; i++)
	{
		int x;
		scanf("%d", &x);
		a[x - 1] = 2;
	}
	
	int ans = 0;
	int bestp = 0;
	for(int i = 0; i < n; i++)
		if(a[i] != 2)
			ans++;
	vector<int> cntl(3);
	vector<int> cntr(3);
	for(int i = 0; i < n; i++)
		cntr[a[i]]++;
	for(int i = 0; i < n; i++)
	{
		cntl[a[i]]++;
		cntr[a[i]]--;
		bestp = max(bestp, cntl[0] - cntl[1]);
		int curans = cntr[0] + cntr[1] + cntl[2] + cntl[0] - bestp;
		ans = min(ans, curans);
	}
	
	cout << ans << endl;
}                    	

#include<bits/stdc++.h>

using namespace std;

typedef long long li;
const int N = 143;
const int K = 15;
const int V = 5000000;

int n;
li a[N];
int lst[V];
map<int, int> nxt[V];
int t = 1;
li a1[N];
li a2[N];

int get_nxt(int v, int x)
{
	if(!nxt[v].count(x))
		nxt[v][x] = t++;
	return nxt[v][x];
}

void add(vector<int> diff, int x)
{
	int v = 0;
	for(auto i : diff)
		v = get_nxt(v, i);
	lst[v] = x;
}

int try_find(vector<int> diff)
{
	int v = 0;
	for(auto i : diff)
	{
		if(!nxt[v].count(i))
			return -1;
		v = nxt[v][i];
	}
	return lst[v];
}

vector<int> get_diff(li arr[N], int x)
{
	vector<int> cnt(n);
	for(int i = 0; i < n; i++)
		cnt[i] = __builtin_popcountll(arr[i] ^ x);
	vector<int> diff(n - 1);
	for(int i = 0; i + 1 < n; i++)
		diff[i] = cnt[i + 1] - cnt[0];
	return diff;
}

int main()
{
	cin >> n;
	for(int i = 0; i < n; i++)
		cin >> a[i];
	
	for(int i = 0; i < n; i++)
	{
		a1[i] = (a[i] >> K);
		a2[i] = a[i] ^ (a1[i] << K);
	}
	for(int i = 0; i < (1 << K); i++)
	{
		vector<int> d = get_diff(a1, i);
		add(d, i);
	}
	for(int i = 0; i < (1 << K); i++)
	{
		vector<int> d = get_diff(a2, i);
		for(int j = 0; j + 1 < n; j++)
			d[j] *= -1;
		int x = try_find(d);
		if(x != -1)
		{
			li res = (li(x) << K) ^ i;
			cout << res << endl;
			return 0;
		}
	}
	cout << -1 << endl;
	return 0;
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

const int LOGN = 18;
const int MOD = 998244353;
int g = 3;

int mul(int a, int b) {
	return int(a * 1ll * b % MOD);
}
int norm(int a) {
	while(a >= MOD) a -= MOD;
	while(a < 0) a += MOD;
	return a;
}
int binPow (int a, int k) {
	int ans = 1;
	for (; k > 0; k >>= 1) {
		if (k & 1)
			ans = mul(ans, a);
		a = mul(a, a);
	}
	return ans;
}
int inv(int a) {
	return binPow(a, MOD - 2);
}

vector<int> w[LOGN], rv;
bool precalced = false;

void precalc() {
	if(precalced)
		return;
	precalced = true;
	
    int wb = binPow(g, (MOD - 1) / (1 << LOGN));
    fore(st, 0, LOGN) {
        w[st].assign(1 << st, 1);

        int bw = binPow(wb, 1 << (LOGN - st - 1));
        int cw = 1;

        fore(k, 0, (1 << st)) {
            w[st][k] = cw;
            cw = mul(cw, bw);
        }
    }
    
    rv.assign(1 << LOGN, 0);
    fore(i, 1, sz(rv))
		rv[i] = (rv[i >> 1] >> 1) | ((i & 1) << (LOGN - 1));
}

const int MX = (1 << LOGN) + 3;

inline void fft(int a[MX], int n, bool inverse) {
	precalc();
	
    int ln = __builtin_ctz(n);
    assert((1 << ln) < MX);
    assert((1 << ln) == n);

    fore(i, 0, n) {
        int ni = rv[i] >> (LOGN - ln);
        if(i < ni) swap(a[i], a[ni]);
    }

    for(int st = 0; (1 << st) < n; st++) {
        int len = (1 << st);
        for(int k = 0; k < n; k += (len << 1)) {
        	fore(pos, k, k + len) {
                int l = a[pos];
                int r = mul(a[pos + len], w[st][pos - k]);

                a[pos] = norm(l + r);
                a[pos + len] = norm(l - r);
            }
        }
    }
    
    if(inverse) {
        int in = inv(n);
        fore(i, 0, n)
            a[i] = mul(a[i], in);
        reverse(a + 1, a + n);
    }
}

int aa[MX], bb[MX], cc[MX];

vector<int> multiply(const vector<int> &a, const vector<int> &b) {
	int ln = 1;
	while(ln < (sz(a) + sz(b)))
		ln <<= 1;
	
	fore(i, 0, ln)
		aa[i] = (i < sz(a) ? a[i] : 0);
	fore(i, 0, ln)
		bb[i] = (i < sz(b) ? b[i] : 0);
		
	fft(aa, ln, false);
	fft(bb, ln, false);
	
	fore(i, 0, ln)
		cc[i] = mul(aa[i], bb[i]);
	fft(cc, ln, true);
	
	vector<int> ans(cc, cc + ln);
	while(ans.back() == 0)
		ans.pop_back();
	return ans;
}

int n;
vector<int> ps;

inline bool read() {
	if(!(cin >> n))
		return false;
	ps.resize(n);
	fore(i, 0, n)
		cin >> ps[i];
	return true;
}

struct cmp {
	bool operator ()(const vector<int> &a, const vector<int> &b) {
		return sz(a) < sz(b);
	}
};

inline void solve() {
	map<int, int> cnt;
	fore (i, 0, n)
		cnt[ps[i]]++;
	
	multiset< vector<int>, cmp > polys;
	for (auto p : cnt)
		polys.emplace(p.second + 1, 1);
	
	while (sz(polys) > 1) {
		auto it2 = polys.begin();
		auto it1 = it2++;
		polys.insert(multiply(*it1, *it2));
		
		polys.erase(it1);
		polys.erase(it2);
	}

	auto poly = *polys.begin();
//	cerr << '[';
//	fore(i, 0, sz(poly)) {
//		if(i) cerr << ", ";
//		cerr << poly[i];
//	}
//	cerr << ']' << endl;

	cout << poly[n / 2] << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

bool ans[26];

void solve() {
	string s;
	cin >> s;
	
	memset(ans, 0, sizeof(ans));
	
	for (int i = 0; i < s.size(); i++) {
		int j = i;
		while (j + 1 < s.size() && s[j + 1] == s[i])
			j++;
		if ((j - i) % 2 == 0)
			ans[s[i] - 'a'] = true;
		i = j;
	}
	
	for (int i = 0; i < 26; i++) if (ans[i])
		cout << char('a' + i);
	cout << endl;
}

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

fun main() {
    val q = readLine()!!.toInt()
    for (ct in 1..q) {
        val n = readLine()!!.toInt()
        var (odd, evenGood, evenBad) = listOf(0, 0, 0)
        for (i in 1..n) {
            val s = readLine()!!
            when {
                s.length % 2 == 1 -> odd++
                s.count { it == '0' } % 2 == 0 -> evenGood++
                else -> evenBad++
            }
        }
        println(n - if (odd == 0 && evenBad % 2 == 1) 1 else 0)
    }
}

#include <bits/stdc++.h>

using namespace std;

int t;
string a;

int main() {	
	cin >> t;
	for(int tc = 0; tc < t; ++tc){
		cin >> a;
		string s[2];
		for(auto x : a)
			s[int(x - '0') & 1] += x;
		
		reverse(s[0].begin(), s[0].end());
		reverse(s[1].begin(), s[1].end());

		string res = "";
		while(!(s[0].empty() && s[1].empty())){
			if(s[0].empty()){
				res += s[1].back();
				s[1].pop_back();
				continue;
			}
			if(s[1].empty()){
				res += s[0].back();
				s[0].pop_back();
				continue;
			}

			if(s[0].back() < s[1].back()){
				res += s[0].back();
				s[0].pop_back();
			}
			else{
				res += s[1].back();
				s[1].pop_back();
			}
		}

		cout << res << endl;
	}	
	return 0;
} 

#include <bits/stdc++.h>

using namespace std;

const int N = int(2e5) + 99;
const int INF = int(1e9) + 100;

int t;
int n;
long long s;
pair<int, int> p[N];

bool ok(int mid){
	long long sum = 0;
	int cnt = 0;
	vector <int> v;
	for(int i = 0; i < n; ++i){
		if(p[i].second < mid)
			sum += p[i].first;
		else if(p[i].first >= mid){
			sum += p[i].first;
			++cnt;
		}
		else
			v.push_back(p[i].first);
	}

	assert(is_sorted(v.begin(), v.end()));
	
	int need = max(0, (n + 1) / 2 - cnt);
	if(need > v.size()) return false;
	for(int i = 0; i < v.size(); ++i){
		if(i < v.size() - need)
			sum += v[i];
		else
			sum += mid;
	}

	return sum <= s;
}

int main() {	
	scanf("%d", &t);
	for(int tc = 0; tc < t; ++tc){
		scanf("%d %lld", &n, &s);
		for(int i = 0; i < n; ++i)
			scanf("%d %d", &p[i].first, &p[i].second);
		
		sort(p, p + n);
		int lf = 1, rg = INF; ///WA -> 10^9
		while(rg - lf > 1){
			int mid = (lf + rg) / 2;
			if(ok(mid)) lf = mid;
			else rg = mid;
		}
		
		printf("%d\n", lf);
	}
	return 0;
}                             	

#include <bits/stdc++.h>

using namespace std;

const int N = int(3e5) + 99;

int t, n;
vector <int> v[N];

int main() {	
	int t;
	scanf("%d", &t);
	for(int tc = 0; tc < t; ++tc){
		scanf("%d", &n);
		for(int i = 0; i < n; ++i)
			v[i].clear();
		for(int i = 0; i < n; ++i){
			int x, s;
			scanf("%d %d", &x, &s);
			v[x].push_back(s);
		}		
		
		multiset <int > q;
		long long res = 0;
		int pref = n;
		int cnt = 0;
		for(int i = n - 1; i >= 0; --i){
			pref -= v[i].size();
			int need = i - pref;
			for(auto x : v[i]) q.insert(x);

			while(cnt < need){
				++cnt;
				res += *q.begin();				
				q.erase(q.begin());
			}
		}		

        	printf("%lld\n", res);
        }
	return 0;
}                             	

#include<bits/stdc++.h>

using namespace std;

const int LOGN = 20;
const int N = (1 << LOGN);
const int MOD = 998244353;
const int g = 3;

#define forn(i, n) for(int i = 0; i < int(n); i++)

inline int mul(int a, int b)
{
	return (a * 1ll * b) % MOD;
}

inline int norm(int a) 
{
	while(a >= MOD)
		a -= MOD;
	while(a < 0)
		a += MOD;
	return a;
}

inline int binPow(int a, int k) 
{
	int ans = 1;
	while(k > 0) 
	{
		if(k & 1)
			ans = mul(ans, a);
		a = mul(a, a);
		k >>= 1;
	}
	return ans;
}

inline int inv(int a) 
{
	return binPow(a, MOD - 2);
}

vector<int> w[LOGN];
vector<int> iw[LOGN];
vector<int> rv[LOGN];

void precalc() 
{
	int wb = binPow(g, (MOD - 1) / (1 << LOGN));
	
	for(int st = 0; st < LOGN; st++) 
	{
		w[st].assign(1 << st, 1);
		iw[st].assign(1 << st, 1);
		
		int bw = binPow(wb, 1 << (LOGN - st - 1));
		int ibw = inv(bw);
		
		int cw = 1;
		int icw = 1;
		
		for(int k = 0; k < (1 << st); k++) 
		{
			w[st][k] = cw;
			iw[st][k] = icw;
			
			cw = mul(cw, bw);
			icw = mul(icw, ibw);
		}
		
		rv[st].assign(1 << st, 0);
		
		if(st == 0) 
		{
			rv[st][0] = 0;
			continue;
		}
		int h = (1 << (st - 1));
		for(int k = 0; k < (1 << st); k++)
			rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
	}
}

inline void fft(int a[N], int n, int ln, bool inverse) 
{	
	for(int i = 0; i < n; i++) 
	{
		int ni = rv[ln][i];
		if(i < ni)
			swap(a[i], a[ni]);
	}
	
	for(int st = 0; (1 << st) < n; st++) 
	{
		int len = (1 << st);
		for(int k = 0; k < n; k += (len << 1)) 
		{
			for(int pos = k; pos < k + len; pos++) 
			{
				int l = a[pos];
				int r = mul(a[pos + len], (inverse ? iw[st][pos - k] : w[st][pos - k]));
				
				a[pos] = norm(l + r);
				a[pos + len] = norm(l - r);
			}
		}
	}
	
	if(inverse) 
	{
		int in = inv(n);
		for(int i = 0; i < n; i++)
			a[i] = mul(a[i], in);
	}
}

int aa[N], bb[N], cc[N];

inline void multiply(int a[N], int sza, int b[N], int szb, int c[N], int &szc) 
{
	int n = 1, ln = 0;
	while(n < (sza + szb))
		n <<= 1, ln++;
	for(int i = 0; i < n; i++)
		aa[i] = (i < sza ? a[i] : 0);
	for(int i = 0; i < n; i++)
		bb[i] = (i < szb ? b[i] : 0);
		
	fft(aa, n, ln, false);
	fft(bb, n, ln, false);
	
	for(int i = 0; i < n; i++)
		cc[i] = mul(aa[i], bb[i]);
		
	fft(cc, n, ln, true);
	
	szc = n;
	for(int i = 0; i < n; i++)
		c[i] = cc[i];
}

vector<int> T[N];

int a[N];
int b[N];
int n, k;
int ans[N];
int Q[N];
int fact[N];
int rfact[N];

int auxa[N];
int auxb[N];
int auxc[N];

int C(int n, int k)
{
	if(n < 0 || k < 0 || k > n) return 0;
	return mul(fact[n], mul(rfact[k], rfact[n - k]));
}

vector<int> newtonExp(int a, int b, int p)
{
	vector<int> res(p + 1);
	for(int i = 0; i <= p; i++)
		res[i] = mul(C(p, i), mul(binPow(a, i), binPow(b, p - i)));
	return res;
}

int main()
{
	precalc();
	fact[0] = 1;
	for(int i = 1; i < N; i++) fact[i] = mul(fact[i - 1], i);
	for(int i = 0; i < N; i++) rfact[i] = inv(fact[i]);
	
	scanf("%d %d", &n, &k);
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);
	for(int i = 0; i < k; i++) scanf("%d", &b[i]);
	int q;
	scanf("%d", &q);
	for(int i = 0; i < q; i++) scanf("%d", &Q[i]);
	
	map<int, int> cnt;
	for(int i = 0; i < n; i++)
		cnt[a[i]]++;
	
	for(int i = 0; i < k; i++)
	{
		int redL = b[i];
		int cnt1 = 0;
		int cnt2 = 0;
		for(auto x : cnt)
		{
			if(x.first >= redL) 
				break;
			if(x.second == 1)
				cnt1++;
			else
				cnt2++;
		}
		memset(auxa, 0, sizeof auxa);
		memset(auxb, 0, sizeof auxb);
		memset(auxc, 0, sizeof auxc);
		vector<int> p1 = newtonExp(2, 1, cnt1);
		vector<int> p2 = newtonExp(1, 1, cnt2 * 2);
		int sa = p1.size();
		int sb = p2.size();
		int sc;
		for(int j = 0; j < sa; j++)
			auxa[j] = p1[j];
		for(int j = 0; j < sb; j++)
			auxb[j] = p2[j];
		multiply(auxa, sa, auxb, sb, auxc, sc);
		for(int j = 0; j < q; j++)
		{
			int cntW = Q[j] / 2 - redL - 1;
			if(cntW >= 0 && cntW < sc)
				ans[j] = norm(ans[j] + auxc[cntW]);
		}
	}
	
	for(int i = 0; i < q; i++)
		printf("%d\n", ans[i]);
}

t = int(input())

for i in range(t):
	x, y = map(int, input().split())
	if(x - y > 1):
		print('YES')
	else:
		print('NO')

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)

const int N = 100 * 1000 + 13;

int n, r;
int a[N];

void solve() {
	scanf("%d%d", &n, &r);
	forn(i, n) scanf("%d", &a[i]);
	
	sort(a, a + n);
	n = unique(a, a + n) - a;
	
	int ans = 0;
	for (int i = n - 1; i >= 0; i--) 
		ans += (a[i] - ans * r > 0);

	printf("%d\n", ans);
}

int main() {
	int q;
	scanf("%d", &q);
	forn(i, q) solve();
}

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

const int INF = int(1e9);

int h, n;
vector<int> p;

inline bool read() {
	if(!(cin >> h >> n))
		return false;
	p.resize(n);
	fore(i, 0, n)
		cin >> p[i];
	return true;
}

inline void solve() {
	int ans = 0;
	
	int lf = 0;
	fore(i, 0, n) {
		if (i > 0 && p[i - 1] > p[i] + 1) {
			if (lf > 0)
				ans += (i - lf) & 1;
			else
				ans += 1 - ((i - lf) & 1);
			lf = i;
		}
	}
	if (p[n - 1] > 1) {
		if (lf != 0)
			ans += (n - lf) & 1;
		else
			ans += 1 - ((n - lf) & 1);
	}
	
	cout << ans << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	int tc; cin >> tc;
	while(tc--) {
		read();
		solve();
	}
	return 0;
}

n = int(input())
s = input()
res = n * (n - 1) // 2

for x in range(2):
	cur = 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			cur += 1
		else:
			res -= cur - x
			cur = 1
	s = s[::-1]

print(res) 

#include <bits/stdc++.h>

using namespace std;

void upd(int &a, int b){
	a = min(a, b);
}

const int N = 20;
const int M = (1 << N) + 55;
const int INF = int(1e9) + 100;

int a, n;
string s;
int cnt[N][N];
int d[M][N];
int dp[M];
int cntBit[M];
int minBit[M];

int main() {	
	cin >> n >> a >> s;
	
	int B = (1 << a) - 1;
	for(int i = 1; i < s.size(); ++i){
		++cnt[s[i] - 'a'][s[i - 1] - 'a'];
		++cnt[s[i - 1] - 'a'][s[i] - 'a'];
	}
	for(int i = 0; i < M; ++i)
		dp[i] = INF;
	dp[0] = 0;
	for(int msk = 1; msk < M; ++msk){
		cntBit[msk] = 1 + cntBit[msk & (msk - 1)];
		for(int i = 0; i < N; ++i) if((msk >> i) & 1){
			minBit[msk] = i;
			break;
		}
	}
	for(int msk = 1; msk < M; ++msk)
		for(int i = 0; i < a; ++i){
			int b = minBit[msk];
			d[msk][i] = d[msk ^ (1 << b)][i] + cnt[i][b];		
		}

	for(int msk = 0; msk < (1 << a); ++msk){
		for(int i = 0; i < a; ++i){
			if((msk >> i) & 1) continue;
			//i -> x
			int pos = cntBit[msk];
			int nmsk = msk | (1 << i);
			upd(dp[nmsk], dp[msk] + pos * (d[msk][i] - d[B ^ nmsk][i]));
		}
	}	

	cout << dp[B] << endl;
	return 0;
} 

#include <bits/stdc++.h>

using namespace std;

const int N = int(3e5) + 99;

int n;
vector <int> g[N];
int d[N];
int dp[N][2];

void dfs(int v, int p){
	vector <int> d1;
	dp[v][1] = d[v] - 1;
	for(auto to : g[v]){
		if(to == p) continue;
		dfs(to, v);
		dp[v][0] = max(dp[v][0], dp[to][0]);
		if(g[to].size() > 1){
			d1.push_back(dp[to][1]);
			dp[v][1] = max(dp[v][1], d[v] + dp[to][1] - 1);	
		}
	}

	sort(d1.rbegin(), d1.rend());
	int x = d[v] + 1;
	for(int i = 0; i < 2; ++i)
		if(i < d1.size())
			x += d1[i];
    dp[v][0] = max(dp[v][0], x);
}

int main() {	
    int q;
    scanf("%d", &q);
    for(int qc = 0; qc < q; ++qc){
    	scanf("%d", &n);
    	for(int i = 0; i < n; ++i){
    	    g[i].clear();
    	    d[i] = 0;
    	    dp[i][0] = dp[i][1] = 0;
    	}
    	for(int i = 0; i < n - 1; ++i){
    		int u, v;
    		scanf("%d %d", &u, &v);
    		--u, --v;
    		g[u].push_back(v), g[v].push_back(u);
    	}
    
        if(n <= 2){
            printf("%d\n", n);
            continue;
        }
        
    	for(int v = 0; v < n; ++v){
    		//d[v] = 1;
    		//for(auto to : g[v])	
    		//	d[v] += g[to].size() == 1;
    		d[v] = g[v].size();
    	}
        
        int r = -1;
        for(int v = 0; v < n; ++v)
            if(g[v].size() != 1)
                r = v;
                
    	dfs(r, r);
    	printf("%d\n", dp[r][0]);
    }
	return 0;
}                             	

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define mp make_pair
#define forn(i, n) for (int i = 0; i < int(n); ++i)

typedef long long li;
typedef pair<int, int> pt;

const int N = 500 * 1000 + 13;

int n, m, c, c0;
pair<int, pt> a[N];

li solve() {
	scanf("%d%d%d%d", &n, &m, &c, &c0);
	forn(i, n) scanf("%d%d%d", &a[i].x, &a[i].y.x, &a[i].y.y);
	a[n++] = mp(m, mp(0, 0));
	sort(a, a + n);

	int sum = c0;
	map<int, int> q;
	q[0] = c0;
	
	li ans = 0;
	forn(i, n) {
		int x = a[i].x;
		int cnt = a[i].y.x;
		int cost = a[i].y.y;
	
		int dist = x - (i ? a[i - 1].x : 0);
		while (!q.empty() && dist > 0) {
			int can = min(q.begin()->y, dist);
			ans += q.begin()->x * 1ll * can;
			sum -= can;
			dist -= can;
			q.begin()->y -= can;
			if (q.begin()->y == 0) q.erase(q.begin());
		}
		
		if (dist > 0) 
			return -1;
		
		int add = min(c - sum, cnt);
		sum += add;
		
		while (add < cnt && !q.empty() && q.rbegin()->x > cost) {
			if (cnt - add >= q.rbegin()->y) {
				add += q.rbegin()->y;
				q.erase(--q.end());
			} else {
				q.rbegin()->y -= cnt - add;
				add = cnt;
			}
		}
		
		q[cost] += add;
	}
	
	return ans;
}

int main() {
	int q;
	scanf("%d", &q);
	forn(i, q) printf("%lld\n", solve());
}

for t in range(int(input())):
	n = input()
	l = filter(lambda x : x <= 2048,  map(int, input().split()) )
	print('YES' if sum(l) >= 2048 else 'NO')

n = int(input())
for i in range(n):
	print(''.join(['W' if (i + j) % 2 == 0 else 'B' for j in range(n)]))

t = int(input())
for i in range(t):
	c, m, x = map(int, input().split())
	d = max(c, m) - min(c, m)
	x += d
	if(c > m):
		c -= d
	else:
		m -= d
	ans = min(c, m, x)
	c -= ans
	m -= ans
	x -= ans
	ans += (c + m) // 3
	print(ans)

#include <bits/stdc++.h>

using namespace std;

int main(){
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i){
		int c, m, x;
		cin >> c >> m >> x;
		int l = 0, r = min(c, m);
		int ans = 0;
		while (l <= r){
			int mid = (l + r) / 2;
			if (c + m + x - 2 * mid >= mid){
				l = mid + 1;
				ans = mid;
			}
			else{
				r = mid - 1;
			}
		}
		cout << ans << "\n";
	}
}

#include <bits/stdc++.h>

using namespace std;

const int N = int(3e5) + 99;
const long long INF64 = (long long)(1e18) + 100;

int t;
int n;
int a[N];
int b[N];
long long dp[3][N];

long long calc(int add, int pos){
	long long &res = dp[add][pos];
	if(res != -1) return res;

	res = INF64;
	if(pos == n) return res = 0;
	for(long long x = 0; x <= 2; ++x)
		if(pos == 0 || a[pos] + x != a[pos - 1] + add)
			res = min(res, calc(x, pos + 1) + x * b[pos]);
		
	return res;
}

int main() {	
	scanf("%d", &t);
	for(int tc = 0; tc < t; ++tc){
		scanf("%d", &n);
		for(int i = 0; i < n; ++i){
			scanf("%d", a + i);
			scanf("%d", b + i);
		}

		for(int i = 0; i <= n; ++i) 
			dp[0][i] = dp[1][i] = dp[2][i] = -1;				
		printf("%lld\n", calc(0, 0));
	}
	return 0;
} 

#include <bits/stdc++.h>

using namespace std;

const int N = int(2e5) + 99;

int t;
int a, b;
string s;

int main() {
	cin >> t;
	for(int tc = 0; tc < t; ++tc){
		cin >> a >> b >> s;
		vector <int> v;
		int l = 0;
		while(l < s.size()){
			if(s[l] == 'X'){
				++l;
				continue;
			}

			int r = l + 1;
			while(r < s.size() && s[r] == '.') ++r;
			v.push_back(r - l);
			l = r;
		}
		
		bool ok = true;
		int id = -1;
		int cnt = 0;
		for(int i = 0; i < v.size(); ++i){
			if(b <= v[i] && v[i] < a) ok = false;
			if(b + b <= v[i]){
				if(id == -1) id = i;
				else ok = false;
			}
			if(a <= v[i] && v[i] < b + b) ++cnt; 
		}

		if(!ok){
			cout << "NO" << endl;			
			continue;
		}

		if(id == -1){
			if(cnt & 1) cout << "YES" << endl;
			else cout << "NO" << endl;
			continue;
		}

		ok = false;
		int sz = v[id];
		assert(sz >= a);
		for(int rem1 = 0; sz - a - rem1 >= 0; ++rem1){
			int rem2 = sz - a - rem1;
			int ncnt = cnt;
			if((rem1 >= b + b) || (b <= rem1 && rem1 < a)) continue;
			if((rem2 >= b + b) || (b <= rem2 && rem2 < a)) continue;

			if(rem1 >= a) ++ncnt;
			if(rem2 >= a) ++ncnt;
			if(ncnt % 2 == 0) ok = true;
		}
		
		if(ok) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}                             	

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define sz(a) int((a).size())
#define forn(i, n) for (int i = 0; i < int(n); ++i)

typedef long long li;
typedef pair<int, int> pt;

const int N = 1000 * 1000 + 13;

int n;
pair<pt, int> a[N];
vector<int> vals;
vector<pt> ev[N];
pair<li, int> t[4 * N];
li add[4 * N];

void build(int v, int l, int r) {
	if (l == r) {
		t[v] = mp(-vals[l], l);
		add[v] = 0;
		return;
	}
	int m = (l + r) >> 1;
	build(v * 2 + 1, l, m);
	build(v * 2 + 2, m + 1, r);
	t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
}

void push(int v, int l, int r) {
	if (add[v] == 0) return;
	t[v].x += add[v];
	if (l != r) {
		add[v * 2 + 1] += add[v];
		add[v * 2 + 2] += add[v];
	}
	add[v] = 0;
}

void upd(int v, int l, int r, int L, int R, int val) {
	push(v, l, r);
	if (L > R) return;
	if (l == L && r == R) {
		add[v] += val;
		push(v, l, r);
		return;
	}
	int m = (l + r) >> 1;
	upd(v * 2 + 1, l, m, L, min(m, R), val);
	upd(v * 2 + 2, m + 1, r, max(m + 1, L), R, val);
	t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
}

pair<li, int> get(int v, int l, int r, int L, int R) {
	push(v, l, r);
	if (L > R) return mp(-li(1e18), 0);
	if (l == L && r == R) return t[v];
	int m = (l + r) >> 1;
	auto r1 = get(v * 2 + 1, l, m, L, min(m, R));
	auto r2 = get(v * 2 + 2, m + 1, r, max(m + 1, L), R);
	return max(r1, r2);
}

int main() {
	scanf("%d", &n);
	forn(i, n) scanf("%d%d%d", &a[i].x.x, &a[i].x.y, &a[i].y);
	
	forn(i, n) {
		vals.pb(a[i].x.x);
		vals.pb(a[i].x.y);
	}
	
	vals.pb(0);
	sort(all(vals));
	vals.pb(vals.back() + 1);
	
	vals.resize(unique(all(vals)) - vals.begin());
	
	forn(i, n) {
		int x = lower_bound(all(vals), a[i].x.x) - vals.begin();
		int y = lower_bound(all(vals), a[i].x.y) - vals.begin();
		ev[min(x, y)].pb(mp(max(x, y), a[i].y));
	}
	
	n = sz(vals);
	
	build(0, 0, n - 1);
	
	li ans = -1;
	int ansl = -1, ansr = -1;
	
	for (int i = sz(vals) - 1; i >= 0; i--) {
		for (auto it : ev[i]) upd(0, 0, n - 1, it.x, n - 1, it.y);
		auto cur = get(0, 0, n - 1, i, n - 1);
		if (cur.x + vals[i] > ans) {
			ans = cur.x + vals[i];
			ansl = vals[i]; ansr = vals[cur.y]; 
		}
	}
	
	printf("%lld\n%d %d %d %d\n", ans, ansl, ansl, ansr, ansr);
	
}

#include <bits/stdc++.h>

using namespace std;

const int N = 40;
const int M = 20;

long long incident_mask[N];
vector<int> g[N];
int n, m;
long long ans = 0;
long long cntmask[1 << M];

long long binpow(long long x, long long y)
{
	long long z = 1;
	while(y > 0)
	{
		if(y % 2 == 1) z *= x;
		x *= x;
		y /= 2;
	}
	return z;
}

int used[N];

void dfs(int x, int c)
{
	if(used[x])
		return;
	used[x] = c;
	for(auto y : g[x])
		dfs(y, 3 - c);
}

long long countIsolated()
{
	long long ans = 0;
	for(int i = 0; i < n; i++)
		if(g[i].empty())
			ans++;
	return ans;
}

long long countComponents()
{
	memset(used, 0, sizeof used);
	long long ans = 0;
	for(int i = 0; i < n; i++)
		if(!used[i])
		{
			ans++;
			dfs(i, 1);
		}
	return ans;
}

bool bipartite()
{
	memset(used, 0, sizeof used);
	for(int i = 0; i < n; i++)
		if(!used[i])
			dfs(i, 1);
	for(int i = 0; i < n; i++)
		for(auto j : g[i])
			if(used[i] == used[j])
				return false;
	return true;
}

long long countIndependentSets()
{
	int m1 = min(n, 20);
	int m2 = n - m1;
	//cerr << m1 << " " << m2 << endl;
	memset(cntmask, 0, sizeof cntmask);
	for(int i = 0; i < (1 << m1); i++)
	{
		long long curmask = 0;
		bool good = true;
		for(int j = 0; j < m1; j++)
		{
			if((i & (1 << j)) == 0)
				continue;
			if(curmask & (1 << j))
				good = false;
			curmask |= ((1 << j) | incident_mask[j]);
		}
		if(good)
		{
			cntmask[curmask >> m1]++;
		}
	}	
	for(int i = 0; i < m2; i++)
		for(int j = 0; j < (1 << m2); j++)
			if(j & (1 << i))
				cntmask[j] += cntmask[j ^ (1 << i)];
	long long ans = 0;
	for(int i = 0; i < (1 << m2); i++)
	{
		long long curmask = 0;
		bool good = true;
		for(int j = m1; j < n; j++)
		{
			if((i & (1 << (j - m1))) == 0)
				continue;
			if(curmask & (1ll << j))
				good = false;
			curmask |= (1ll << j) | incident_mask[j];
		}
		if(good)
		{
			//cerr << i << endl;
			ans += cntmask[(i ^ ((1 << m2) - 1))];
		}
	}
	return ans;
}

long long calc(int mask)
{
	if(mask == 0)
		return binpow(2, n);
	if(mask == 1 || mask == 4)
		return countIndependentSets();
	if(mask == 2)
		return binpow(2, countComponents());
	if(mask == 3 || mask == 6)
		return binpow(2, countIsolated());
	if(mask == 5)
		return (bipartite() ? binpow(2, countComponents()) : 0);
	if(mask == 7)
		return (m == 0 ? binpow(2, n) : 0);
	return 0;
}

int main() {
	cin >> n >> m;
	for(int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;
		--x;
		--y;
		g[x].push_back(y);
		g[y].push_back(x);
		incident_mask[x] ^= (1ll << y);
		incident_mask[y] ^= (1ll << x);
	}
	for(int i = 0; i < 8; i++)
	{
		//cerr << i << " " << calc(i) << endl;
		if(__builtin_popcount(i) % 2 == 0)
			ans += calc(i);
		else
			ans -= calc(i);
	}
	cout << ans << endl;
    return 0;
}