t = int(input())
for i in range(t):
    x, y = map(int, input().split())
    if y % x != 0:
        print(0, 0)
    else:
        print(1, y // x)

#include <bits/stdc++.h>
 
using namespace std;
 
int main() 
{
    string w = "aa";
    map<string, int> idx;
    int i = 1;
    for(w[0] = 'a'; w[0] <= 'z'; w[0]++)
        for(w[1] = 'a'; w[1] <= 'z'; w[1]++)
            if(w[0] != w[1])
                idx[w] = i++;
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        string s;
        cin >> s;
        cout << idx[s] << endl;
    }   
}

for _ in range(int(input())):
    s = input()
    t = input()
    if t == "a":
        print(1)
    elif t.count('a') != 0:
        print(-1)
    else:
        print(2**len(s))
        

fun main() {
    repeat(readLine()!!.toInt()) {
        val n = readLine()!!.toInt()
        val a = readLine()!!.split(' ').map { it.toInt() }.toIntArray()
        for (i in (n % 2) until n step 2) {
            if (a[i] > a[i + 1])
                a[i] = a[i + 1].also { a[i + 1] = a[i] }
        }
        var sorted = true
        for (i in a.indices)
            if (i > 0 && a[i - 1] > a[i])
                sorted = false
        println(if(sorted) "YES" else "NO")
    }
}

#include <iostream>
#include <sstream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <string>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <ctime>
#include <cmath>

#define forn(i, n) for(int i=0;i<n;++i)
#define fore(i, l, r) for(int i = int(l); i <= int(r); ++i)
#define sz(v) int(v.size())
#define all(v) v.begin(), v.end()
#define pb push_back
#define mp make_pair
#define x first
#define y1 ________y1
#define y second
#define ft first
#define sc second
#define pt pair<int, int>

template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
template<typename X> inline X sqr(const X& a) { return a * a; }

typedef long long li;
typedef long double ld;

using namespace std;

const int INF = 1000 * 1000 * 1000;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);

const int N = 200 * 1000 + 13;

int n;
int a[N];

inline void read() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }   
}

inline void solve() {   
    int ans = INF;
    for (int i = 0; i < n - 1; i++) {
        int cur = 0;
        int x = a[i], y = a[i + 1];
        if (x < y) {
            swap(x, y);
        }
        int cnt = min(x - y, (x + 1) / 2);
        cur += cnt;
        x -= 2 * cnt;
        y -= cnt;
        if (x > 0 && y > 0) {
            cur += (x + y + 2) / 3;
        }
        ans = min(ans, cur);    
    }

    for (int i = 0; i < n - 2; i++) {
        int cur = 0;
        int x = a[i], y = a[i + 2];
        if (x < y) {
            swap(x, y);
        }
        int cnt = (x - y + 1) / 2;
        cur += cnt;
        cur += y;
        ans = min(ans, cur);
    }
    
    sort(a, a + n);
    ans = min(ans, (a[0] + 1) / 2 + (a[1] + 1) / 2);
    cout << ans << endl;
}

int main () {
#ifdef fcspartakm
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    srand(time(NULL));
    cerr << setprecision(10) << fixed;
    
    read();
    solve();
 
    //cerr << "TIME: " << clock() << endl;
}

#include <bits/stdc++.h>

using namespace std;

static char buf[1010];

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
    
    int n, m, q;
    scanf("%d %d %d", &n, &m, &q);
    vector<string> tmp(n);
    string s;
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        scanf("%s", buf);
        tmp[i] = buf;
        sum += count(tmp[i].begin(), tmp[i].end(), '*');
    }
    
    for (int j = 0; j < m; ++j) {
        for (int i = 0; i < n; ++i) {
            s += tmp[i][j];
        }
    }
    int res = count(s.begin(), s.begin() + sum, '.');
    int pos = sum;
    for (int i = 0; i < q; ++i) {
        int x, y;
        scanf("%d %d", &x, &y);
        --x, --y;
        int p = y * n + x;
        if (p < pos) {
            if (s[p] == '.') {
                --res;
            } else {
                ++res;
            }
        }
        s[p] = (s[p] == '.' ? '*' : '.');
        if (s[p] == '*') {
            if (s[pos] == '.') {
                ++res;
            }
            ++pos;
        } else {
            if (s[pos - 1] == '.') {
                --res;
            }
            --pos;
        }
        printf("%d\n", res);
    }
    
    return 0;
}

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
const int INF = 1e9;
 
vector<int> in, out;
vector<vector<int>> g;
vector<int> dp;
 
int calc(int v){
    if (dp[v] != -1) return dp[v];
    if (in[v] >= 2 && out[v] >= 2){
        dp[v] = 1;
        for (int u : g[v])
            dp[v] = max(dp[v], calc(u) + 1);
    }
    else if (in[v] >= 2){
        dp[v] = 1;
    }
    else{
        dp[v] = -INF;
    }
    return dp[v];
}
 
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    g.resize(n);
    in.resize(n);
    out.resize(n);
    forn(i, m){
        int v, u;
        scanf("%d%d", &v, &u);
        --v, --u;
        g[v].push_back(u);
        ++in[u];
        ++out[v];
    }
    int ans = 1;
    dp.resize(n, -1);
    forn(v, n) if (out[v] >= 2){
        for (int u : g[v]){
            ans = max(ans, calc(u) + 1);
        }
    }
    printf("%d\n", ans);
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		for (int i = 0; i < n; ++i) {
			cout << (i + 1) % n + 1 << " ";
		}
		cout << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> cnt(n + 1), idx(n + 1);
		for (int i = 0; i < n; ++i) {
			int x;
			cin >> x;
			++cnt[x];
			idx[x] = i + 1;
		}
		int ans = -1;
		for (int i = 0; i <= n; ++i) {
			if (cnt[i] == 1) {
				ans = idx[i];
				break;
			}
		}
		cout << ans << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> a(n);
		for (auto &it : a) cin >> it;
		vector<int> res(n + 1, 1);
		n = unique(a.begin(), a.end()) - a.begin();
		a.resize(n);
		for (int i = 0; i < n; ++i) {
			res[a[i]] += 1;
		}
		res[a[0]] -= 1;
		res[a[n - 1]] -= 1;
		int ans = 1e9;
		for (int i = 0; i < n; ++i) {
			ans = min(ans, res[a[i]]);
		}
		cout << ans << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		long long n;
		cin >> n;
	
		vector<pair<int, long long>> val;
		for (long long i = 2; i * i <= n; ++i) {
			int cnt = 0;
			while (n % i == 0) {
				++cnt;
				n /= i;
			}
			if (cnt > 0) {
				val.push_back({cnt, i});
			}
		}
		if (n > 1) {
			val.push_back({1, n});
		}
	
		sort(val.rbegin(), val.rend());
		vector<long long> ans(val[0].first, val[0].second);
		for (int i = 1; i < int(val.size()); ++i) {
			for (int j = 0; j < val[i].first; ++j) {
				ans.back() *= val[i].second;
			}
		}
	
		cout << ans.size() << endl;
		for (auto it : ans) cout << it << " ";
		cout << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<set<int>> g(n);
		for (int i = 0; i < n; ++i) {
			int x, y;
			cin >> x >> y;
			--x, --y;
			g[x].insert(y);
			g[y].insert(x);
		}
		vector<int> val(n, 1);
		queue<int> leafs;
		for (int i = 0; i < n; ++i) {
			if (g[i].size() == 1) {
				leafs.push(i);
			}
		}
		while (!leafs.empty()) {
			int v = leafs.front();
			leafs.pop();
			int to = *g[v].begin();
			val[to] += val[v];
			val[v] = 0;
			g[v].clear();
			g[to].erase(v);
			if (g[to].size() == 1) {
				leafs.push(to);
			}
		}
		long long ans = 0;
		for (int i = 0; i < n; ++i) {
			ans += val[i] * 1ll * (val[i] - 1) / 2;
			ans += val[i] * 1ll * (n - val[i]);
		}
		cout << ans << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

bool found;

void shift(multiset<int> &l, multiset<int> &r, int val) {
	l.erase(l.find(val));
	r.insert(val);
}

void check(const multiset<int> &lf, const multiset<int> &mid, const multiset<int> &rg) {
	if (found || lf.empty() || mid.empty() || rg.empty()) {
		return;
	}
	if (*lf.rbegin() == *mid.begin() && *mid.begin() == *rg.rbegin()) {
		found = true;
		cout << "YES" << endl;
		cout << lf.size() << " " << mid.size() << " " << rg.size() << endl;
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> a(n);
		for (auto &it : a) cin >> it;
		
		found = false;
		multiset<int> lf, mid(a.begin(), a.end()), rg;
		int r = n - 1;
		for (int l = 0; l < n - 2; ++l) {
			shift(mid, lf, a[l]);
			while (r - 1 >= l && a[r] <= *lf.rbegin()) {
				shift(mid, rg, a[r]);
				--r;
			}
			
			while (r - 1 < l) {
				shift(rg, mid, a[r + 1]);
				++r;
			}
			
			check(lf, mid, rg);
			
			shift(lf, mid, a[l]);
			check(lf, mid, rg);
			shift(mid, lf, a[l]);
			
			if (rg.empty()) continue;
			
			shift(rg, mid, a[r + 1]);
			check(lf, mid, rg);
			shift(mid, rg, a[r + 1]);
		}
		if (!found) {
			cout << "NO" << endl;
		}
	}
	
	return 0;
}

// Author: Ivan Kazmenko (gassa@mail.ru)
module solution;
import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.string;

void main ()
{
	auto tests = readln.strip.to !(int);
	foreach (test; 0..tests)
	{
		auto n = readln.strip.to !(int);
		auto a = readln.splitter.map !(to !(int)).array;
		auto x = a.dup;
		foreach (i; 1..n)
		{
			x[i] = max (x[i], x[i - 1]);
		}
		auto y = a.dup;
		foreach_reverse (i; 0..n - 1)
		{
			y[i] = max (y[i], y[i + 1]);
		}

		auto v = a.maxElement;
		auto maxPlaces = n.iota.filter !(i => a[i] == v).array;
		int lo = maxPlaces[$ / 2];
		int hi = lo + 1;

		while (true)
		{
			if (lo == 0 || hi == n)
			{
				writeln ("NO");
				break;
			}
			if (x[lo - 1] == v && y[hi] == v)
			{
				writeln ("YES");
				writeln (lo, " ", hi - lo, " ", n - hi);
				break;
			}
			int u = (lo - 1 == 0) ? int.min :
			    min (x[lo - 2], a[lo - 1]);
			int w = (hi + 1 >= n) ? int.min :
			    min (y[hi + 1], a[hi]);
			if (u > w)
			{
				v = min (v, a[lo - 1]);
				lo -= 1;
			}
			else
			{
				v = min (v, a[hi]);
				hi += 1;
			}
		}
	}
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		string x;
		cin >> x;
		int dig = x[0] - '0' - 1;
		int len = x.size();
		cout << dig * 10 + len * (len + 1) / 2 << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> a(n);
		for (auto &it : a) cin >> it;
		while (a.back() == 0) a.pop_back();
		reverse(a.begin(), a.end());
		while (a.back() == 0) a.pop_back();
		cout << count(a.begin(), a.end(), 0) << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> a(n);
		int mx = 0;
		for (auto &it : a) {
			cin >> it;
			mx = max(mx, it);
		}
		int idx = -1;
		for (int i = 0; i < n; ++i) {
			if (a[i] != mx) continue;
			if (i > 0 && a[i - 1] != mx) idx = i + 1;
			if (i < n - 1 && a[i + 1] != mx) idx = i + 1;
		}
		cout << idx << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> a(n);
		for (auto &it : a) cin >> it;
		vector<pair<int, int>> res;
		int idx = -1;
		for (int i = 1; i < n; ++i) {
			if (a[i] != a[0]) {
				idx = i;
				res.push_back({1, i + 1});
			}
		}
		if (idx == -1) {
			cout << "NO" << endl;
			continue;
		}
		for (int i = 1; i < n; ++i) {
			if (a[i] == a[0]) {
				res.push_back({idx + 1, i + 1});
			}
		}
		cout << "YES" << endl;
		for (auto [x, y] : res) cout << x << " " << y << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 21;

long long f[N];

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	f[0] = 1;
	for (int i = 1; i < N; ++i) {
		f[i] = f[i - 1] * i;
	}
	
	long long ans = f[n] / f[n / 2] / f[n / 2];
	ans = ans * f[n / 2 - 1];
	ans = ans * f[n / 2 - 1];
	ans /= 2;
	
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

const int N = 75;
const int INF = 1e9;

int a[N][N];
int dp[N][N][N][N];

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, m, k;
	cin >> n >> m >> k;
	forn(i, n) forn(j, m) {
		cin >> a[i][j];
	}
	
	forn(i, N) forn(j, N) forn(cnt, N) forn(rem, N) dp[i][j][cnt][rem] = -INF;
	dp[0][0][0][0] = 0;
	forn(i, n) forn(j, m) forn(cnt, m / 2 + 1) forn(rem, k) {
		if (dp[i][j][cnt][rem] == -INF) continue;
		int ni = (j == m - 1 ? i + 1 : i);
		int nj = (j == m - 1 ? 0 : j + 1);
		if (i != ni) {
			dp[ni][nj][0][rem] = max(dp[ni][nj][0][rem], dp[i][j][cnt][rem]);
		} else {
			dp[ni][nj][cnt][rem] = max(dp[ni][nj][cnt][rem], dp[i][j][cnt][rem]);
		}
		if (cnt + 1 <= m / 2) {
			int nrem = (rem + a[i][j]) % k;
			if (i != ni) {
				dp[ni][nj][0][nrem] = max(dp[ni][nj][0][nrem], dp[i][j][cnt][rem] + a[i][j]);
			} else {
				dp[ni][nj][cnt + 1][nrem] = max(dp[ni][nj][cnt + 1][nrem], dp[i][j][cnt][rem] + a[i][j]);
			}
		}
	}
	
	cout << max(0, dp[n][0][0][0]) << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int n;
vector<vector<int>> d;
vector<vector<pair<int, int>>> g;

void dijkstra(int s, vector<int> &d) {
	d = vector<int>(n, INF);
	d[s] = 0;
	set<pair<int, int>> st;
	st.insert({d[s], s});
	while (!st.empty()) {
		int v = st.begin()->second;
		st.erase(st.begin());
		for (auto [to, w] : g[v]) {
			if (d[to] > d[v] + w) {
				auto it = st.find({d[to], to});
				if (it != st.end()) st.erase(it);
				d[to] = d[v] + w;
				st.insert({d[to], to});
			}
		}
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int m, k;
	cin >> n >> m >> k;
	g = vector<vector<pair<int, int>>>(n);
	for (int i = 0; i < m; ++i) {
		int x, y, w;
		cin >> x >> y >> w;
		--x, --y;
		g[x].push_back({y, w});
		g[y].push_back({x, w});
	}
	
	vector<pair<int, int>> r(k);
	for (auto &[a, b] : r) {
		cin >> a >> b;
		--a, --b;
	}
	
	d = vector<vector<int>>(n);
	for (int v = 0; v < n; ++v) {
		dijkstra(v, d[v]);
	}
	
	int ans = INF;
	for (int v = 0; v < n; ++v) {
		for (auto [to, w] : g[v]) {
			int cur = 0;
			for (auto [a, b] : r) {
				cur += min({d[a][b], d[a][v] + d[to][b], d[a][to] + d[v][b]});
			}
			ans = min(ans, cur);
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

for i in range(int(input())):
    n, x = map(int, input().split())
    print(1 if n <= 2 else (n - 3) // x + 2)

for i in range(int(input())):
	n, m = map(int, input().split())
	a = []
	for i in range(n):
		a.append([[int(x) for x in input().split()] for i in range(2)])
	ok = False
	for i in range(n):
		ok |= a[i][0][1] == a[i][1][0]
	ok &= m % 2 == 0
	print("YES" if ok else "NO") 

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		int ans = 1e9;
		for (int x = 1; x * x <= n; ++x) {
			ans = min(ans, x - 1 + ((n - x) + x - 1) / x);
		}
		cout << ans << endl;
	}
	
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

const long double EPS = 1e-9;

long long f(long long x)
{                                                        
	long long z = sqrtl(x);
	long long ans = 1e18;
	for(int i = -5; i <= 5; i++)
	{
	 	long long z2 = z - i;
	 	if(z2 > x || z2 < 1)
	 		continue;
	 	ans = min(ans, z2 - 2 + (x + z2 - 1) / z2);
	}
	return ans;
}

int main()
{
 	int t;
 	cin >> t;
 	for(int i = 0; i < t; i++)
 	{
 	 	long long x;
 	 	cin >> x;
 	 	cout << f(x) << endl;
 	}
}

n = int(input())
a = [int(x) for x in input().split()]
d = set()
d.add(0)
cur = 0
ans = 0
for i in range(n):
	cur += a[i]
	if cur in d:
		ans += 1
		d = set()
		d.add(0)
		cur = a[i]
	d.add(cur)
print(ans)

#include <bits/stdc++.h>

#define sz(v) int(v.size())
#define all(v) v.begin(), v.end()
#define pb push_back
#define ft first
#define sc second

using namespace std;

int n;
vector<int> a, b;

inline void read() {
	cin >> n;
	a.resize(3);
	b.resize(3);
	for (int i = 0; i < 3; i++) cin >> a[i];
	for (int i = 0; i < 3; i++) cin >> b[i];
}
	
inline void solve() {
	int ans1 = INT_MAX;
	vector<pair<int, int> > ord;
	ord.pb({0, 0});
	ord.pb({0, 2});
	ord.pb({1, 1});
	ord.pb({1, 0});
	ord.pb({2, 2});
	ord.pb({2, 1});
	sort(all(ord));
	do {
		vector<int> a1 = a, b1 = b;
		for (int i = 0; i < sz(ord); i++) {
			int cnt = min(a1[ord[i].ft], b1[ord[i].sc]);
			a1[ord[i].ft] -= cnt;
			b1[ord[i].sc] -= cnt;			
		}
		int cur = min(a1[0], b1[1]) + min(a1[1], b1[2]) + min(a1[2], b1[0]);
		ans1 = min(ans1, cur);
	} while(next_permutation(all(ord)));
	int ans2 = min(a[0], b[1]) + min(a[1], b[2]) + min(a[2], b[0]);
	cout << ans1 << ' ' << ans2 << endl;
}

int main () {
    read();
    solve();
}

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

const int MOD = int(1e9) + 7;
const int N = 200043;
const int K = 4;

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 n;
string s;
int dp[N][K][K];
char buf[N];
int pow3[N];

int main() {
	scanf("%d", &n);
	scanf("%s", buf);
	s = buf;
	int cntQ = 0;
	for(auto c : s)
		if(c == '?')
			cntQ++;
	pow3[0] = 1;
	for(int i = 1; i < N; i++)
		pow3[i] = mul(pow3[i - 1], 3);
	dp[0][0][0] = 1;
	for(int i = 0; i < n; i++)
		for(int j = 0; j <= 3; j++)
			for(int k = 0; k <= 3; k++)
			{
			 	if(!dp[i][j][k]) continue;
			 	dp[i + 1][j][k] = add(dp[i + 1][j][k], dp[i][j][k]);
			 	if(j < 3 && (s[i] == '?' || s[i] - 'a' == j))
			 	{
			 	 	int nk = (s[i] == '?' ? k + 1 : k);
			 	 	dp[i + 1][j + 1][nk] = add(dp[i + 1][j + 1][nk], dp[i][j][k]);
			 	}
		   	}
	int ans = 0;
	for(int i = 0; i <= 3; i++)
		if(cntQ >= i)
			ans = add(ans, mul(dp[n][3][i], pow3[cntQ - i]));
	printf("%d\n", ans);
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int a, b;
		cin >> a >> b;
		cout << (abs(a - b) + 9) / 10 << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int a, b, x, y, n;
		cin >> a >> b >> x >> y >> n;
		long long ans = 1e18;
		for (int i = 0; i < 2; ++i) {
			int da = min(n, a - x);
			int db = min(n - da, b - y);
			ans = min(ans, (a - da) * 1ll * (b - db));
			swap(a, b);
			swap(x, y);
		}
		cout << ans << endl;
	}
	
	return 0;
}

// Author: Ivan Kazmenko (gassa@mail.ru)
module solution;
import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.string;

void main ()
{
	auto tests = readln.strip.to !(int);
	foreach (test; 0..tests)
	{
		int n, x, y;
		readf !(" %s %s %s") (n, x, y);
		auto answer = int.max.repeat (n).array;
		foreach (start; 1..51)
		{
			foreach (d; 1..51)
			{
				auto a = iota (start, start + d * n, d).array;
				if (a.canFind (x) && a.canFind (y))
				{
					if (answer.back > a.back)
					{
						answer = a;
					}
				}
			}
		}
		writefln !("%(%s %)") (answer);
	}
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n, x, y;
		cin >> n >> x >> y;
		vector<int> ans;
		for (int d = 1; d <= y - x; ++d) {
			if ((y - x) % d != 0) continue;
			vector<int> res;
			bool foundx = false;
			int cur = y;
			int need = n;
			while (cur >= 1 && need > 0) {
				res.push_back(cur);
				foundx |= cur == x;
				--need;
				cur -= d;
			}
			cur = y;
			while (need > 0) {
				cur += d;
				res.push_back(cur);
				--need;
			}
			sort(res.begin(), res.end());
			if (need == 0 && foundx) {
				if (ans.empty() || ans.back() > res.back()) {
					ans = res;
				}
			}
		}
		assert(!ans.empty());
		for (auto it : ans) cout << it << " ";
		cout << endl;
		
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
    int tcs;
    cin >> tcs;

    while (tcs--) {
        int n, x, y;
        cin >> n >> x >> y;
        int diff = y - x;
        for (int delta = 1; delta <= diff; ++delta) {
            if (diff % delta) continue;
            if (diff / delta + 1 > n) continue;
            int k = min((y - 1) / delta, n - 1);
            int a0 = y - k * delta;
            for (int i = 0; i < n; ++i) {
                cout << (a0 + i * delta) << ' ';
            }
            cout << endl;
            break;
        }
    }
}

#include <bits/stdc++.h>

using namespace std;

int sum(long long n) {
	int res = 0;
	while (n > 0) {
		res += n % 10;
		n /= 10;
	}
	return res;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		long long n;
		int s;
		cin >> n >> s;
		long long ans = 0;
		if (sum(n) <= s) {
			cout << 0 << endl;
			continue;
		}
		long long pw = 1;
		for (int i = 0; i < 18; ++i) {
			int digit = (n / pw) % 10;
			long long add = pw * ((10 - digit) % 10);
			n += add;
			ans += add;
			if (sum(n) <= s) {
				break;
			}
			pw *= 10;
		}
		cout << ans << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n, k;
		cin >> n >> k;
		vector<int> x(n), y(n);
		for (auto &it : x) cin >> it;
		for (auto &it : y) cin >> it;
		sort(x.begin(), x.end());
		int j = n - 1;
		vector<int> l(n), r(n);
		for (int i = n - 1; i >= 0; --i) {
			while (x[j] - x[i] > k) --j;
			r[i] = j - i + 1;
			if (i + 1 < n) r[i] = max(r[i], r[i + 1]);
		}
		j = 0;
		for (int i = 0; i < n; ++i) {
			while (x[i] - x[j] > k) ++j;
			l[i] = i - j + 1;
			if (i > 0) l[i] = max(l[i], l[i - 1]);
		}
		int ans = 1;
		for (int i = 0; i < n - 1; ++i) {
			ans = max(ans, r[i + 1] + l[i]);
		}
		cout << ans << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	string s, t;
	cin >> n >> k >> s >> t;
	vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, -INF)));
	dp[0][0][0] = 0;
	for (int i = 0; i < n; ++i) {
		for (int ck = 0; ck <= k; ++ck) {
			for (int cnt0 = 0; cnt0 <= n; ++cnt0) {
				if (dp[i][ck][cnt0] == -INF) continue;
				int e0 = s[i] == t[0];
				int e1 = s[i] == t[1];
				int e01 = t[0] == t[1];
				
				dp[i + 1][ck][cnt0 + e0] = max(dp[i + 1][ck][cnt0 + e0], dp[i][ck][cnt0] + (e1 ? cnt0 : 0));
				
				if (ck < k) {
					dp[i + 1][ck + 1][cnt0 + 1] = max(dp[i + 1][ck + 1][cnt0 + 1], dp[i][ck][cnt0] + (e01 ? cnt0 : 0));
					dp[i + 1][ck + 1][cnt0 + e01] = max(dp[i + 1][ck + 1][cnt0 + e01], dp[i][ck][cnt0] + cnt0);
				}
			}
		}
	}
	
	int ans = 0;
	for (int ck = 0; ck <= k; ++ck) {
		for (int cnt0 = 0; cnt0 <= n; ++cnt0) {
			ans = max(ans, dp[n][ck][cnt0]);
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

// Author: Ivan Kazmenko (gassa@mail.ru)
module solution;
import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.string;

void main ()
{
	int n, k;
	while (readf !(" %s %s") (n, k) > 0)
	{
		readln;
		auto s0 = readln.strip;
		auto t = readln.strip;
		auto s = s0.dup;
		int res = 0;
		foreach (b0; 0..k + 1)
		{
			auto e0 = k - b0;
loop_x0:
			foreach (x0; 0..b0 + 1)
			{
loop_y0:
				foreach (y0; 0..e0 + 1)
				{
					int b = b0;
					int e = e0;
					int x = x0;
					int y = y0;
					s[] = s0[];
					for (int i = 0; i < n && b; i++)
					{
						if (s[i] == t[0])
						{
						}
						else if (s[i] != t[1])
						{
							s[i] = t[0];
							b -= 1;
						}
						else if (x > 0)
						{
							s[i] = t[0];
							x -= 1;
							b -= 1;
						}
					}

					for (int j = n - 1; j >= 0 && e; j--)
					{
						if (s[j] == t[1])
						{
						}
						else if (s[j] != t[0])
						{
							s[j] = t[1];
							e -= 1;
						}
						else if (y > 0)
						{
							s[j] = t[1];
							y -= 1;
							e -= 1;
						}
					}

					int cur = 0;
					int add = 0;
					for (int i = 0; i < n; i++)
					{
						if (s[i] == t[1])
						{
							cur += add;
						}
						if (s[i] == t[0])
						{
							add += 1;
						}
					}
					res = max (res, cur);

					if (x > 0)
					{
						break loop_x0;
					}
					if (y > 0)
					{
						break loop_y0;
					}
				}
			}
		}

		writeln (res);
	}
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> a(n);
		for (auto &it : a) cin >> it;
		sort(a.begin(), a.end());
		bool ok = true;
		for (int i = 1; i < n; ++i) {
			ok &= (a[i] - a[i - 1] <= 1);
		}
		if (ok) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> a(n), b(n);
		for (auto &it : a) cin >> it;
		for (auto &it : b) cin >> it;
		int mna = *min_element(a.begin(), a.end());
		int mnb = *min_element(b.begin(), b.end());
		long long ans = 0;
		for (int i = 0; i < n; ++i) {
			ans += max(a[i] - mna, b[i] - mnb);
		}
		cout << ans << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> cnt(n + 1);
		for (int i = 0; i < n; ++i) {
			int x;
			cin >> x;
			++cnt[x];
		}
		int ans = 0;
		for (int s = 2; s <= 2 * n; ++s) {
			int cur = 0;
			for (int i = 1; i < (s + 1) / 2; ++i) {
				if (s - i > n) continue;
				cur += min(cnt[i], cnt[s - i]);
			}
			if (s % 2 == 0) cur += cnt[s / 2] / 2;
			ans = max(ans, cur);
		}
		cout << ans << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		string s;
		cin >> n >> s;
		vector<int> ans(n);
		vector<int> pos0, pos1;
		for (int i = 0; i < n; ++i) {
			int newpos = pos0.size() + pos1.size();
			if (s[i] == '0') {
				if (pos1.empty()) {
					pos0.push_back(newpos);
				} else {
					newpos = pos1.back();
					pos1.pop_back();
					pos0.push_back(newpos);
				}
			} else {
				if (pos0.empty()) {
					pos1.push_back(newpos);
				} else {
					newpos = pos0.back();
					pos0.pop_back();
					pos1.push_back(newpos);
				}
			}
			ans[i] = newpos;
		}
		cout << pos0.size() + pos1.size() << endl;
		for (auto it : ans) cout << it + 1 << " ";
		cout << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

vector<int> w, cnt;
vector<vector<pair<int, int>>> g;

long long getdiff(int i) {
	return w[i] * 1ll * cnt[i] - (w[i] / 2) * 1ll * cnt[i];
}

void dfs(int v, int p = -1) {
	if (g[v].size() == 1) cnt[p] = 1;
	for (auto [to, id] : g[v]) {
		if (id == p) continue;
		dfs(to, id);
		if (p != -1) cnt[p] += cnt[id];
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		long long s;
		cin >> n >> s;
		w = cnt = vector<int>(n - 1);
		g = vector<vector<pair<int, int>>>(n);
		for (int i = 0; i < n - 1; ++i) {
			int x, y;
			cin >> x >> y >> w[i];
			--x, --y;
			g[x].push_back({y, i});
			g[y].push_back({x, i});
		}
		dfs(0);
		set<pair<long long, int>> st;
		long long cur = 0;
		for (int i = 0; i < n - 1; ++i) {
			st.insert({getdiff(i), i});
			cur += w[i] * 1ll * cnt[i];
		}
		cerr << cur << endl;
		int ans = 0;
		while (cur > s) {
			int id = st.rbegin()->second;
			st.erase(prev(st.end()));
			cur -= getdiff(id);
			w[id] /= 2;
			st.insert({getdiff(id), id});
			++ans;
		}
		cout << ans << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int n;
vector<int> w, c, cnt;
vector<vector<pair<int, int>>> g;

long long getdiff(int i) {
	return w[i] * 1ll * cnt[i] - (w[i] / 2) * 1ll * cnt[i];
}

void dfs(int v, int p = -1) {
	if (g[v].size() == 1) cnt[p] = 1;
	for (auto [to, id] : g[v]) {
		if (id == p) continue;
		dfs(to, id);
		if (p != -1) cnt[p] += cnt[id];
	}
}

vector<long long> get(int clr) {
	set<pair<long long, int>> st;
	long long cur = 0;
	for (int i = 0; i < n - 1; ++i) {
		if (c[i] == clr) {
			st.insert({getdiff(i), i});
			cur += w[i] * 1ll * cnt[i];
		}
	}
	vector<long long> res;
	res.push_back(cur);
	while (cur > 0 && !st.empty()) {
		int id = st.rbegin()->second;
		st.erase(prev(st.end()));
		cur -= getdiff(id);
		res.push_back(cur);
		w[id] /= 2;
		st.insert({getdiff(id), id});
	}
	return res;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		long long s;
		cin >> n >> s;
		w = c = cnt = vector<int>(n - 1);
		g = vector<vector<pair<int, int>>>(n);
		for (int i = 0; i < n - 1; ++i) {
			int x, y;
			cin >> x >> y >> w[i] >> c[i];
			--x, --y;
			g[x].push_back({y, i});
			g[y].push_back({x, i});
		}
		dfs(0);
		vector<long long> v1 = get(1), v2 = get(2);
		int pos = int(v2.size()) - 1;
		int ans = INF;
		for (int i = 0; i < int(v1.size()); ++i) {
			while (pos > 0 && v1[i] + v2[pos - 1] <= s) --pos;
			if (v1[i] + v2[pos] <= s) {
				ans = min(ans, i + pos * 2);
			}
		}
		cout << ans << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> rg;
vector<vector<int>> dp;

int calc(int l, int r) {
	if (dp[l][r] != -1) return dp[l][r];
	dp[l][r] = 0;
	if (l > r) return dp[l][r];
	bool add = count(rg[l].begin(), rg[l].end(), r); // can't be greater than 1
	dp[l][r] = max(dp[l][r], add + (l + 1 > r ? 0 : calc(l + 1, r)));
	for (auto nr : rg[l]) {
		if (nr >= r) continue;
		dp[l][r] = max(dp[l][r], add + calc(l, nr) + (nr + 1 > r ? 0 : calc(nr + 1, r)));
	}
	return dp[l][r];
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> l(n), r(n);
		vector<int> val;
		for (int i = 0; i < n; ++i) {
			cin >> l[i] >> r[i];
			val.push_back(l[i]);
			val.push_back(r[i]);
		}
		sort(val.begin(), val.end());
		val.resize(unique(val.begin(), val.end()) - val.begin());
		for (int i = 0; i < n; ++i) {
			l[i] = lower_bound(val.begin(), val.end(), l[i]) - val.begin();
			r[i] = lower_bound(val.begin(), val.end(), r[i]) - val.begin();
		}
		int siz = val.size();
		dp = vector<vector<int>>(siz, vector<int>(siz, -1));
		rg = vector<vector<int>>(siz);
		for (int i = 0; i < n; ++i) {
			rg[l[i]].push_back(r[i]);
		}
		cout << calc(0, siz - 1) << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		vector<int> a(3);
		for (auto &it : a) cin >> it;
		sort(a.begin(), a.end());
		if (a[1] != a[2]) {
			cout << "NO" << endl;
		} else {
			cout << "YES" << endl << a[0] << " " << a[0] << " " << a[2] << endl;
		}
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> a(2 * n);
		for (auto &it : a) cin >> it;
		vector<int> used(n);
		vector<int> p;
		for (int i = 0; i < 2 * n; ++i) {
			if (!used[a[i] - 1]) {
				used[a[i] - 1] = true;
				p.push_back(a[i]);
			}
		}
		for (auto it : p) cout << it << " ";
		cout << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> a(n);
		for (auto &it : a) cin >> it;
		int pos = n - 1;
		while (pos > 0 && a[pos - 1] >= a[pos]) --pos;
		while (pos > 0 && a[pos - 1] <= a[pos]) --pos;
		cout << pos << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int calc(const string &s, char c) {
	if (s.size() == 1) {
		return s[0] != c;
	}
	int mid = s.size() / 2;
	int cntl = calc(string(s.begin(), s.begin() + mid), c + 1);
	cntl += s.size() / 2 - count(s.begin() + mid, s.end(), c);
	int cntr = calc(string(s.begin() + mid, s.end()), c + 1);
	cntr += s.size() / 2 - count(s.begin(), s.begin() + mid, c);
	return min(cntl, cntr);
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		string s;
		cin >> n >> s;
		cout << calc(s, 'a') << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

vector<int> ord;
vector<int> used;
vector<vector<int>> g;

void dfs(int v) {
	used[v] = 1;
	for (auto to : g[v]) {
		if (!used[to]) dfs(to);
	}
	ord.push_back(v);
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n, m;
		cin >> n >> m;
		g = vector<vector<int>>(n);
		vector<pair<int, int>> edges;
		for (int i = 0; i < m; ++i) {
			int t, x, y;
			cin >> t >> x >> y;
			--x, --y;
			if (t == 1) {
				g[x].push_back(y);
			}
			edges.push_back({x, y});
		}
		
		ord.clear();
		used = vector<int>(n);
		for (int i = 0; i < n; ++i) {
			if (!used[i]) dfs(i);
		}
		vector<int> pos(n);
		reverse(ord.begin(), ord.end());
		for (int i = 0; i < n; ++i) {
			pos[ord[i]] = i;
		}
		bool bad = false;
		for (int i = 0; i < n; ++i) {
			for (auto j : g[i]) {
				if (pos[i] > pos[j]) bad = true;
			}
		}
		if (bad) {
			cout << "NO" << endl;
		} else {
			cout << "YES" << endl;
			for (auto [x, y] : edges) {
				if (pos[x] < pos[y]) {
					cout << x + 1 << " " << y + 1 << endl;
				} else {
					cout << y + 1 << " " << x + 1 << endl;
				}
			}
		}
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int n, k, ans;
vector<set<int>> g;
vector<set<int>> leaves;

struct comp {
	bool operator() (int a, int b) const {
		if (leaves[a].size() == leaves[b].size()) return a < b;
		return leaves[a].size() > leaves[b].size();
	}
};

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		cin >> n >> k;
		g = leaves = vector<set<int>>(n);
		for (int i = 0; i < n - 1; ++i) {
			int x, y;
			cin >> x >> y;
			--x, --y;
			g[x].insert(y);
			g[y].insert(x);
		}
		for (int i = 0; i < n; ++i) {
			if (g[i].size() == 1) {
				leaves[*g[i].begin()].insert(i);
			}
		}
		set<int, comp> st;
		for (int i = 0; i < n; ++i) {
			st.insert(i);
		}
		int ans = 0;
		while (true) {
			int v = *st.begin();
			if (int(leaves[v].size()) < k) break;
			for (int i = 0; i < k; ++i) {
				int leaf = *leaves[v].begin();
				g[leaf].erase(v);
				g[v].erase(leaf);
				st.erase(v);
				st.erase(leaf);
				leaves[v].erase(leaf);
				if (leaves[leaf].count(v)) leaves[leaf].erase(v);
				if (g[v].size() == 1) {
					int to = *g[v].begin();
					st.erase(to);
					leaves[to].insert(v);
					st.insert(to);
				}
				st.insert(v);
				st.insert(leaf);
				
			}
			ans += 1;
		}
		cout << ans << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int cnt0, cnt1;
vector<int> col, comp;
vector<vector<pair<int, int>>> g;

void dfs(int v, int c, int cmp) {
	col[v] = c;
	if (col[v] == 0) ++cnt0;
	else ++cnt1;
	comp[v] = cmp;
	for (auto [to, change] : g[v]) {
		if (col[to] == -1) {
			dfs(to, c ^ change, cmp);
		}
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<vector<int>> a(2, vector<int>(n));
		vector<vector<int>> pos(n);
		for (int i = 0; i < 2; ++i) {
			for (int j = 0; j < n; ++j) {
				cin >> a[i][j];
				--a[i][j];
				pos[a[i][j]].push_back(j);
			}
		}
		bool bad = false;
		g = vector<vector<pair<int, int>>>(n);
		for (int i = 0; i < n; ++i) {
			if (pos[i].size() != 2) {
				bad = true;
				break;
			}
			int c1 = pos[i][0], c2 = pos[i][1];
			if (c1 == c2) continue;
			int r1 = a[0][c1] != i, r2 = a[0][c2] != i;
			g[c1].push_back({c2, r1 == r2});
			g[c2].push_back({c1, r1 == r2});
		}
		col = comp = vector<int>(n, -1);
		int cnt = 0;
		vector<pair<int, int>> colcnt;
		int ans = 0;
		for (int i = 0; i < n; ++i) {
			if (col[i] == -1) {
				cnt0 = cnt1 = 0;
				dfs(i, 0, cnt);
				++cnt;
				colcnt.push_back({cnt0, cnt1});
				ans += min(cnt0, cnt1);
			}
		}
		for (int i = 0; i < n; ++i) {
			for (auto [j, diff] : g[i]) {
				if ((col[i] ^ col[j]) != diff) {
					bad = true;
				}
			}
		}
		if (bad) {
			cout << -1 << endl;
		} else {
			cout << ans << endl;
			for (int i = 0; i < n; ++i) {
				int changeZero = colcnt[comp[i]].first < colcnt[comp[i]].second;
				if (col[i] ^ changeZero) {
					cout << i + 1 << " ";
				}
			}
			cout << endl;
		}
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int x, y, n;
		cin >> x >> y >> n;
		if (n - n % x + y <= n) {
			cout << n - n % x + y << endl;
		} else {
			cout << n - n % x - (x - y) << endl;
		}
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		int cnt2 = 0, cnt3 = 0;
		while (n % 2 == 0) {
			n /= 2;
			++cnt2;
		}
		while (n % 3 == 0) {
			n /= 3;
			++cnt3;
		}
		if (n == 1 && cnt2 <= cnt3) {
			cout << 2 * cnt3 - cnt2 << endl;
		} else {
			cout << -1 << endl;
		}
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		string s;
		cin >> n >> s;
		int ans = 0;
		int bal = 0;
		for (int i = 0; i < n; ++i) {
			if (s[i] == '(') ++bal;
			else {
				--bal;
				if (bal < 0) {
					bal = 0;
					++ans;
				}
			}
		}
		cout << ans << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

	int t;
	cin >> t;
	while (t--) {
		int n, k;
		cin >> n >> k;
		vector<int> a(n);
		for (auto &it : a) cin >> it;
		map<int, int> cnt;
		int mx = 0;
		for (auto &it : a) {
			if (it % k == 0) continue;
			++cnt[k - it % k];
			mx = max(mx, cnt[k - it % k]);
		}
		long long ans = 0;
		for (auto [key, value] : cnt) {
			if (value == mx) {
				ans = k * 1ll * (value - 1) + key + 1;
			}
		}
		cout << ans << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int INF = 2e9 + 1;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	cin >> n >> k;
	vector<int> times[4];
	vector<int> sums[4];
	for (int i = 0; i < n; ++i) {
		int t, a, b;
		cin >> t >> a >> b;
		times[a * 2 + b].push_back(t);
	}
	for (int i = 0; i < 4; ++i) {
		sort(times[i].begin(), times[i].end());
		sums[i].push_back(0);
		for (auto it : times[i]) {
			sums[i].push_back(sums[i].back() + it);
		}
	}
	
	int ans = INF;
	for (int cnt = 0; cnt < min(k + 1, int(sums[3].size())); ++cnt) {
		if (k - cnt < int(sums[1].size()) && k - cnt < int(sums[2].size())) {
			ans = min(ans, sums[3][cnt] + sums[1][k - cnt] + sums[2][k - cnt]);
		}
	}
	
	if (ans == INF) ans = -1;
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int INF = 2e9 + 1;

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

void updateSt(set<pair<int, int>> &st, set<pair<int, int>> &fr, int &sum, int need) {
	need = max(need, 0);
	while (true) {
		bool useful = false;
		while (size(st) > need) {
			sum -= st.rbegin()->first;
			fr.insert(*st.rbegin());
			st.erase(prev(st.end()));
			useful = true;
		}
		while (size(st) < need && size(fr) > 0) {
			sum += fr.begin()->first;
			st.insert(*fr.begin());
			fr.erase(fr.begin());
			useful = true;
		}
		while (!st.empty() && !fr.empty() && fr.begin()->first < st.rbegin()->first) {
			sum -= st.rbegin()->first;
			sum += fr.begin()->first;
			fr.insert(*st.rbegin());
			st.erase(prev(st.end()));
			st.insert(*fr.begin());
			fr.erase(fr.begin());
			useful = true;
		}
		if (!useful) break;
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, m, k;
	cin >> n >> m >> k;
	vector<pair<int, int>> times[4];
	vector<int> sums[4];
	for (int i = 0; i < n; ++i) {
		int t, a, b;
		cin >> t >> a >> b;
		times[a * 2 + b].push_back({t, i});
	}
	for (int i = 0; i < 4; ++i) {
		sort(times[i].begin(), times[i].end());
		sums[i].push_back(0);
		for (auto it : times[i]) {
			sums[i].push_back(sums[i].back() + it.first);
		}
	}
	
	int ans = INF;
	int pos = INF;
	set<pair<int, int>> st;
	set<pair<int, int>> fr;
	int sum = 0;
	vector<int> res;
	for (int iter = 0; iter < 2; ++iter) {
		st.clear();
		fr.clear();
		sum = 0;
		int start = 0;
		while (k - start >= size(sums[1]) || k - start >= size(sums[2]) || m - start - (k - start) * 2 < 0) {
			++start;
		}
		if (start >= size(sums[3])) {
			cout << -1 << endl;
			return 0;
		}
		int need = m - start - (k - start) * 2;
		for (int i = 0; i < 3; ++i) {
			for (int p = size(times[i]) - 1; p >= (i == 0 ? 0 : k - start); --p) {
				fr.insert(times[i][p]);
			}
		}
		updateSt(st, fr, sum, need);
		for (int cnt = start; cnt < (iter == 0 ? size(sums[3]) : pos); ++cnt) {
			if (k - cnt >= 0) {	
				if (cnt + (k - cnt) * 2 + size(st) == m) {
					if (ans > sums[3][cnt] + sums[1][k - cnt] + sums[2][k - cnt] + sum) {
						ans = sums[3][cnt] + sums[1][k - cnt] + sums[2][k - cnt] + sum;
						pos = cnt + 1;
					}
				}
			} else {
				if (cnt + size(st) == m) {
					if (ans > sums[3][cnt] + sum) {
						ans = sums[3][cnt] + sum;
						pos = cnt + 1;
					}
				}
			}
			if (iter == 1 && cnt + 1 == pos) break;
			need -= 1;
			if (k - cnt > 0) {
				need += 2;
				fr.insert(times[1][k - cnt - 1]);
				fr.insert(times[2][k - cnt - 1]);
			}
			updateSt(st, fr, sum, need);
		}
		if (iter == 1) {
			for (int i = 0; i + 1 < pos; ++i) res.push_back(times[3][i].second);
			for (int i = 0; i <= k - pos; ++i) {
				res.push_back(times[1][i].second);
				res.push_back(times[2][i].second);
			}
			for (auto [value, position] : st) res.push_back(position);
		}
	}
	
	cout << ans << endl;
	for (auto it : res) cout << it + 1 << " ";
	cout << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	auto make = [](vector<int> &a, int pos) {
		swap(a[pos + 1], a[pos + 2]);
		swap(a[pos], a[pos + 1]);
	};

	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> a(n);
		vector<pair<int, int>> res(n);
		for (int i = 0; i < n; ++i) {
			cin >> a[i];
			res[i] = { a[i], i };
		}
		sort(res.begin(), res.end());
		for (int i = 0; i < n; ++i) {
			a[res[i].second] = i;
		}
		int cnt = 0;
		for (int i = 0; i < n; ++i) {
			for (int j = i + 1; j < n; ++j) {
				cnt += a[j] < a[i];
			}
		}
		if (cnt & 1) {
			for (int i = 0; i < n - 1; ++i) {
				if (res[i].first == res[i + 1].first) {
					swap(a[res[i].second], a[res[i + 1].second]);
					break;
				}
			}
		}
		vector<int> ans;
		for (int i = 0; i < n - 2; ++i) {
			int pos = min_element(a.begin() + i, a.end()) - a.begin();
			while (pos > i + 1) {
				make(a, pos - 2);
				ans.push_back(pos - 2);
				pos -= 2;
			}
			if (pos != i) {
				make(a, i);
				make(a, i);
				ans.push_back(i);
				ans.push_back(i);
				pos = i;
			}
		}
		for (int i = 0; i < 3; ++i) {
			if (is_sorted(a.begin(), a.end())) {
				break;
			}
			make(a, n - 3);
			ans.push_back(n - 3);
		}
		if (!is_sorted(a.begin(), a.end())) {
			cout << -1 << endl;
		} else {
			cout << ans.size() << endl;
			for (auto it : ans) cout << it + 1 << " ";
			cout << endl;
		}
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n, m;
		cin >> n >> m;
		cout << min(2, n - 1) * m << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n, k;
		cin >> n >> k;
		vector<int> a(n);
		for (auto &it : a) cin >> it;
		vector<int> b(n);
		for (auto &it : b) cin >> it;
		sort(a.begin(), a.end());
		sort(b.rbegin(), b.rend());
		int ans = 0;
		for (int i = 0; i < n; ++i) {
			if (i < k) ans += max(a[i], b[i]);
			else ans += a[i];
		}
		cout << ans << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		long long ans = 0;
		for (int i = 1; i <= n / 2; ++i) {
			ans += i * 1ll * i;
		}
		cout << ans * 8 << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

struct cmp {
	bool operator() (const pair<int, int> &a, const pair<int, int> &b) const {
		int lena = a.second - a.first + 1;
		int lenb = b.second - b.first + 1;
		if (lena == lenb) return a.first < b.first;
		return lena > lenb;
	}
};

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		set<pair<int, int>, cmp> segs;
		segs.insert({0, n - 1});
		vector<int> a(n);
		for (int i = 1; i <= n; ++i) {
			pair<int, int> cur = *segs.begin();
			segs.erase(segs.begin());
			int id = (cur.first + cur.second) / 2;
			a[id] = i;
			if (cur.first < id) segs.insert({cur.first, id - 1});
			if (id < cur.second) segs.insert({id + 1, cur.second});
		}
		for (auto it : a) cout << it << " ";
		cout << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	auto solve = [](const string &s) {
		int n = s.size();
		int all = count(s.begin(), s.end(), '1');
		int ans = all;
		vector<int> res(n);
		int pref = 0;
		for (int i = 0; i < n; ++i) {
			int cur = (s[i] == '1');
			pref += cur;
			res[i] = 1 - cur;
			if (i > 0) res[i] += min(res[i - 1], pref - cur);
			ans = min(ans, res[i] + all - pref);
		}
		return ans;
	};
	
	int t;
	cin >> t;
	while (t--) {
		int n, k;
		string s;
		cin >> n >> k >> s;
		vector<string> val(k);
		int cnt = count(s.begin(), s.end(), '1');
		for (int i = 0; i < n; ++i) {
			val[i % k] += s[i];
		}
		int ans = 1e9;
		for (auto &it : val) ans = min(ans, solve(it) + (cnt - count(it.begin(), it.end(), '1')));
		cout << ans << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

const long long INF64 = 1e18;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n, m;
		cin >> n >> m;
		vector<vector<long long>> a(n, vector<long long>(m));
		forn(i, n) forn(j, m) {
			cin >> a[i][j];
		}
		long long a00 = a[0][0];
		long long ans = INF64;
		forn(x, n) forn(y, m) {
			long long need = a[x][y] - x - y;
			if (need > a00) continue;
			a[0][0] = need;
			vector<vector<long long>> dp(n, vector<long long>(m, INF64));
			dp[0][0] = a00 - need;
			forn(i, n) forn(j, m) {
				long long need = a[0][0] + i + j;
				if (need > a[i][j]) continue;
				if (i > 0) dp[i][j] = min(dp[i][j], dp[i - 1][j] + a[i][j] - need);
				if (j > 0) dp[i][j] = min(dp[i][j], dp[i][j - 1] + a[i][j] - need);
			}
			ans = min(ans, dp[n - 1][m - 1]);
		}
		cout << ans << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> ans;
		int power = 1;
		while (n > 0) {
			if (n % 10 > 0) {
				ans.push_back((n % 10) * power);
			}
			n /= 10;
			power *= 10;
		}
		cout << ans.size() << endl;
		for (auto number : ans) cout << number << " ";
		cout << endl;
	}
}

#include <bits/stdc++.h>

using namespace std;

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n, k;
		cin >> n >> k;
		int n1 = n - (k - 1);
		if (n1 > 0 && n1 % 2 == 1) {
			cout << "YES" << endl;
			for (int i = 0; i < k - 1; ++i) cout << "1 ";
			cout << n1 << endl;
			continue;
		}
		int n2 = n - 2 * (k - 1);
		if (n2 > 0 && n2 % 2 == 0) {
			cout << "YES" << endl;
			for (int i = 0; i < k - 1; ++i) cout << "2 ";
			cout << n2 << endl;
			continue;
		}
		cout << "NO" << endl;
	}
}

#include <bits/stdc++.h>

using namespace std;

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n, k;
		cin >> n >> k;
		int need = (k - 1) / (n - 1);
		cout << k + need << endl;
	}
}

#include <bits/stdc++.h>

using namespace std;

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> a(n);
		for (auto &it : a) cin >> it;
		int l = 0, r = n - 1;
		int suml = 0, sumr = 0;
		int cnt = 0, ansl = 0, ansr = 0;
		while (l <= r) {
			if (cnt % 2 == 0) {
				int nsuml = 0;
				while (l <= r && nsuml <= sumr) {
					nsuml += a[l++];
				}
				ansl += nsuml;
				suml = nsuml;
			} else {
				int nsumr = 0;
				while (l <= r && nsumr <= suml) {
					nsumr += a[r--];
				}
				ansr += nsumr;
				sumr = nsumr;
			}
			++cnt;
		}
		cout << cnt << " " << ansl << " " << ansr << endl;
	}
}

// Author: Ivan Kazmenko (gassa@mail.ru)
import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.string;

void main ()
{
	auto tests = readln.strip.to !(int);
	foreach (test; 0..tests)
	{
		auto n = readln.strip.to !(int);
		auto a = readln.splitter.map !(to !(int)).array;
		int [2] total;
		int prev = 0;
		int moves = 0;
		while (!a.empty)
		{
			moves += 1;
			int cur = 0;
			while (!a.empty && cur <= prev)
			{
				cur += a[0];
				a = a[1..$];
			}
			total[moves % 2] += cur;
			prev = cur;
			reverse (a);
		}
		writeln (moves, " ", total[1], " ", total[0]);
	}
}

#include <bits/stdc++.h>

using namespace std;

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> a(n);
		vector<int> cnt(n + 1);
		int ans = 0;
		for (auto &it : a) {
			cin >> it;
			++cnt[it];
		}
		for (int l = 0; l < n; ++l) {
			int sum = 0;
			for (int r = l; r < n; ++r) {
				sum += a[r];
				if (l == r) continue;
				if (sum <= n) {
					ans += cnt[sum];
					cnt[sum] = 0;
				}
			}
		}
		cout << ans << endl;
	}
}

#include <bits/stdc++.h>

using namespace std;


int main() {
	int t;
	cin >> t;
	while (t--) {
		int n0, n1, n2;
		cin >> n0 >> n1 >> n2;
		if (n1 == 0) {
			if (n0 != 0) {
				cout << string(n0 + 1, '0') << endl;
			} else {
				cout << string(n2 + 1, '1') << endl;
			}
			continue;
		}
		string ans;
		for (int i = 0; i < n1 + 1; ++i) {
			if (i & 1) ans += "0";
			else ans += "1";
		}
		ans.insert(1, string(n0, '0'));
		ans.insert(0, string(n2, '1'));
		cout << ans << endl;
	}
}

#include <bits/stdc++.h>

using namespace std;

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		if (n < 4) {
			cout << -1 << endl;
			continue;
		}
		for (int i = n; i >= 1; --i) {
			if (i & 1) cout << i << " ";
		}
		cout << 4 << " " << 2 << " ";
		for (int i = 6; i <= n; i += 2) {
			cout << i << " ";
		}
		cout << endl;
	}
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		for (int pw = 2; pw < 30; ++pw) {
			int val = (1 << pw) - 1;
			if (n % val == 0) {
				cerr << val << endl;
				cout << n / val << endl;
				break;
			}
		}
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		n /= 2;
		if (n & 1) {
			cout << "NO" << endl;
			continue;
		}
		cout << "YES" << endl;
		for (int i = 1; i <= n; ++i) {
			cout << i * 2 << " ";
		}
		for (int i = 1; i < n; ++i) {
			cout << i * 2 - 1 << " ";
		}
		cout << 3 * n - 1 << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	auto sgn = [&](int x) {
		if (x > 0) return 1;
		else return -1;
	};

	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> a(n);
		for (auto &it : a) cin >> it;
		long long sum = 0;
		for (int i = 0; i < n; ++i) {
			int cur = a[i];
			int j = i;
			while (j < n && sgn(a[i]) == sgn(a[j])) {
				cur = max(cur, a[j]);
				++j;
			}
			sum += cur;
			i = j - 1;
		}
		cout << sum << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n, k;
		cin >> n >> k;
		vector<int> a(n);
		for (auto &it : a) cin >> it;
		vector<int> cnt(2 * k + 1);
		for (int i = 0; i < n / 2; ++i) {
			++cnt[a[i] + a[n - i - 1]];
		}
		vector<int> pref(2 * k + 2);
		for (int i = 0; i < n / 2; ++i) {
			int l1 = 1 + a[i], r1 = k + a[i];
			int l2 = 1 + a[n - i - 1], r2 = k + a[n - i - 1];
			assert(max(l1, l2) <= min(r1, r2));
			++pref[min(l1, l2)];
			--pref[max(r1, r2) + 1];
		}
		for (int i = 1; i <= 2 * k + 1; ++i) {
			pref[i] += pref[i - 1];
		}
		int ans = 1e9;
		for (int sum = 2; sum <= 2 * k; ++sum) {
			ans = min(ans, (pref[sum] - cnt[sum]) + (n / 2 - pref[sum]) * 2);
		}
		cout << ans << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

vector<vector<int>> g;

void bfs(int s, vector<int> &d) {
	d[s] = 0;
	queue<int> q;
	q.push(s);
	while (!q.empty()) {
		int v = q.front();
		q.pop();
		for (auto to : g[v]) {
			if (d[to] == INF) {
				d[to] = d[v] + 1;
				q.push(to);
			}
		}
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n, m, a, b, c;
		cin >> n >> m >> a >> b >> c;
		--a, --b, --c;
		
		vector<int> p(m);
		for (auto &it : p) cin >> it;
		sort(p.begin(), p.end());
		vector<long long> pref(m + 1);
		for (int i = 0; i < m; ++i) {
			pref[i + 1] = pref[i] + p[i];
		}
		
		g = vector<vector<int>>(n);
		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);
		}
		
		vector<int> da(n, INF), db(n, INF), dc(n, INF);
		bfs(a, da);
		bfs(b, db);
		bfs(c, dc);
		
		long long ans = 1e18;
		for (int i = 0; i < n; ++i) {
			if (da[i] + db[i] + dc[i] > m) continue;
			ans = min(ans, pref[db[i]] + pref[da[i] + db[i] + dc[i]]);
		}
		cout << ans << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<set<int>> segs;
		for (int i = 0; i < n - 1; ++i) {
			set<int> cur;
			int k;
			cin >> k;
			for (int j = 0; j < k; ++j) {
				int x;
				cin >> x;
				cur.insert(x);
			}
			segs.push_back(cur);
		}
		for (int fst = 1; fst <= n; ++fst) {
			vector<int> ans;
			bool ok = true;
			vector<set<int>> cur = segs;
			for (auto &it : cur) if (it.count(fst)) it.erase(fst);
			ans.push_back(fst);
			for (int i = 1; i < n; ++i) {
				int cnt1 = 0;
				int nxt = -1;
				for (auto  &it : cur) if (it.size() == 1) {
					++cnt1;
					nxt = *it.begin();
				}
				if (cnt1 != 1) {
					ok = false;
					break;
				}
				for (auto &it : cur) if (it.count(nxt)) it.erase(nxt);
				ans.push_back(nxt);
			}
			if (ok) {
				set<set<int>> all(segs.begin(), segs.end());
				for (int i = 1; i < n; ++i) {
					set<int> seg;
					seg.insert(ans[i]);
					bool found = false;
					for (int j = i - 1; j >= 0; --j) {
						seg.insert(ans[j]);
						if (all.count(seg)) {
							found = true;
							all.erase(seg);
							break;
						}
					}
					if (!found) ok = false;
				}
			}
			if (ok) {
				for (auto it : ans) cout << it << " ";
				cout << endl;
				break;
			}
		}
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		cout << (n - 1) / 2 << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n, a, b;
		cin >> n >> a >> b;
		for (int i = 0; i < n; ++i) {
			cout << char('a' + i % b);
		}
		cout << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> cnt(n + 1);
		for (int i = 0; i < n; ++i) {
			int x;
			cin >> x;
			++cnt[x];
		}
		int mx = *max_element(cnt.begin(), cnt.end());
		int diff = n + 1 - count(cnt.begin(), cnt.end(), 0);
		cout << max(min(mx - 1, diff), min(mx, diff - 1)) << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		for (int i = 0; i < 9; ++i) {
			string s;
			cin >> s;
			for (auto &c : s) if (c == '2') c = '1';
			cout << s << endl;
		}
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define sz(a) int((a).size())
#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)

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> a(n);
		for (auto &it : a) cin >> it;
		vector<vector<int>> cnt(26, vector<int>(n + 1));
		forn(i, n) {
			forn(j, 26) cnt[j][i + 1] = cnt[j][i];
			++cnt[a[i] - 1][i + 1];
		}
		int ans = 0;
		forn(i, 26) ans = max(ans, cnt[i][n - 1]);
		forn(l, n) fore(r, l, n) {
			int cntin = 0, cntout = 0;
			forn(el, 26) {
				cntin = max(cntin, cnt[el][r + 1] - cnt[el][l]);
				cntout = max(cntout, min(cnt[el][l], cnt[el][n] - cnt[el][r + 1]) * 2);
			}
			ans = max(ans, cntin + cntout);
		}
		cout << ans << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> a(n);
		for (auto &it : a) cin >> it;
		vector<vector<int>> cnt(200, vector<int>(n + 1));
		vector<vector<int>> pos(200);
		forn(i, n) {
			forn(j, 200) cnt[j][i + 1] = cnt[j][i];
			++cnt[a[i] - 1][i + 1];
			pos[a[i] - 1].push_back(i);
		}
		int ans = 0;
		forn(i, 200) {
			ans = max(ans, sz(pos[i]));
			forn(p, sz(pos[i]) / 2) {
				int l = pos[i][p] + 1, r = pos[i][sz(pos[i]) - p - 1] - 1;
				forn(el, 200) {
					int sum = cnt[el][r + 1] - cnt[el][l];
					ans = max(ans, (p + 1) * 2 + sum);
				}
			}
		}
		cout << ans << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int n, m, lognm;
vector<string> c, s;
vector<vector<int>> used, nxt;

void getnext(int x, int y, int &nx, int &ny) {
	if (s[x][y] == 'U') nx = x - 1, ny = y;
	if (s[x][y] == 'R') nx = x, ny = y + 1;
	if (s[x][y] == 'D') nx = x + 1, ny = y;
	if (s[x][y] == 'L') nx = x, ny = y - 1;
}

void dfs(int x, int y) {
	used[x][y] = 1;
	int nx = -1, ny = -1;
	getnext(x, y, nx, ny);
	assert(0 <= nx && nx < n && 0 <= ny && ny < m);
	int v = x * m + y, to = nx * m + ny;
	if (!used[nx][ny]) dfs(nx, ny);
	nxt[v][0] = to;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		cin >> n >> m;
		lognm = 0;
		int nm = n * m;
		while ((1 << lognm) <= nm) ++lognm;
		c = s = vector<string>(n);
		for (auto &it : c) cin >> it;
		for (auto &it : s) cin >> it;
		
		used = vector<vector<int>>(n, vector<int>(m));
		nxt = vector<vector<int>>(n * m, vector<int>(lognm));
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				if (!used[i][j]) dfs(i, j);
			}
		}
		for (int deg = 1; deg < lognm; ++deg) {
			for (int i = 0; i < n; ++i) {
				for (int j = 0; j < m; ++j) {
					int id = i * m + j;
					nxt[id][deg] = nxt[nxt[id][deg - 1]][deg - 1];
				}
			}
		}
		
		vector<vector<int>> black, white;
		black = white = vector<vector<int>>(n, vector<int>(m));
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				int v = i * m + j, to = v;
				for (int deg = lognm - 1; deg >= 0; --deg) {
					if ((nm >> deg) & 1) to = nxt[to][deg];
				}
				if (c[i][j] == '0') ++black[to / m][to % m];
				else ++white[to / m][to % m];
			}
		}
		
		int all = 0, good = 0;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				if (black[i][j]) {
					++all;
					++good;
				} else if (white[i][j]) {
					++all;
				}
			}
		}
		cout << all << " " << good << endl;
	}
	
	return 0;
}

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

const int N = 1e6 + 7;
const int K = 24;

int f[N];
int dp[N];
int ndp[N];
int sel[N];

int fans[N];
int sans[N];

void solve() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < m; j++) {
			sel[i * m + j] = (s[j] == '0');
		}
	}
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < m; j++) {
			int to = -1;
			if (s[j] == 'U') to = (i - 1) * m + j;
			if (s[j] == 'D') to = (i + 1) * m + j;
			if (s[j] == 'L') to = i * m + (j - 1);
			if (s[j] == 'R') to = i * m + (j + 1);
			f[i * m + j] = to;
		}
	}
	n *= m;
	for (int i = 0; i < n; i++) {
		dp[i] = f[i];
	}
	for (int j = 0; j < K; j++) {
		for (int i = 0; i < n; i++) {
			ndp[i] = dp[dp[i]];
		}
		for (int i = 0; i < n; i++) {
			dp[i] = ndp[i];
		}
	}
	fill(fans, fans + n, 0);
	fill(sans, sans + n, 0);
	for (int i = 0; i < n; i++) {
		fans[dp[i]]++;
		sans[dp[i]] += sel[i];
	}
	int fs = 0, ss = 0;
	for (int i = 0; i < n; i++) {
		fs += (fans[i] > 0);
		ss += (sans[i] > 0);
	}
	cout << fs << ' ' << ss << '\n';
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

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

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int a, b;
		cin >> a >> b;
		if (a % b == 0) cout << 0 << endl;
		else cout << b - a % b << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        int n, k;
        cin >> n >> k;
        string s(n, 'a');
        for (int i = n - 2; i >= 0; i--) {
            if (k <= (n - i - 1)) {
                s[i] = 'b';
                s[n - k] = 'b';
                cout << s << endl;
                break;
            }
            k -= (n - i - 1);
        }
    }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		string x;
		cin >> n >> x;
		string a(n, '0'), b(n, '0');
		for (int i = 0; i < n; ++i) {
			if (x[i] == '1') {
				a[i] = '1';
				b[i] = '0';
				for (int j = i + 1; j < n; ++j) {
					b[j] = x[j];
				}
				break;
			} else {
				a[i] = b[i] = '0' + (x[i] - '0') / 2;
			}
		}
		cout << a << endl << b << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int solve() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	
	if (count(a.begin(), a.end(), a[0]) == n) {
		cout << 1 << endl;
		for (int i = 0; i < n; ++i) {
			cout << 1 << " ";
		}
		cout << endl;
		return 0;
	}
	
	if (n % 2 == 0) {
		cout << 2 << endl;
		for (int i = 0; i < n; ++i) {
			cout << i % 2 + 1 << " ";
		}
		cout << endl;
		return 0;
	}
	
	for (int i = 0; i < n; ++i) {
		if (a[i] == a[(i + 1) % n]) {
			vector<int> ans(n);
			for (int j = 0, pos = i + 1; pos < n; ++pos, j ^= 1) {
				ans[pos] = j + 1;
			}
			for (int j = 0, pos = i; pos >= 0; --pos, j ^= 1) {
				ans[pos] = j + 1;
			}
			cout << 2 << endl;
			for (int pos = 0; pos < n; ++pos) {
				cout << ans[pos] << " ";
			}
			cout << endl;
			return 0;
		}
	}
	
	cout << 3 << endl;
	for (int i = 0; i < n - 1; ++i) {
		cout << i % 2 + 1 << " ";
	}
	cout << 3 << endl;
    return 0;    
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

int q;
cin >> q;
for (int qq = 0; qq < q; qq++) {
    solve();
}

	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int T;
vector<int> p, d;
vector<int> tin, tout;
vector<vector<int>> g;

void dfs(int v, int par = -1, int dep = 0) {
	p[v] = par;
	d[v] = dep;
	tin[v] = T++;
	for (auto to : g[v]) {
		if (to == par) continue;
		dfs(to, v, dep + 1);
	}
	tout[v] = T++;
}

bool isAnc(int v, int u) {
	return tin[v] <= tin[u] && tout[u] <= tout[v];
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, m;
	cin >> n >> m;
	T = 0;
	p = d = vector<int>(n);
	tin = tout = vector<int>(n);
	g = vector<vector<int>>(n);
	for (int i = 0; i < n - 1; ++i) {
		int x, y;
		cin >> x >> y;
		--x, --y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(0);
	
	for (int i = 0; i < m; ++i) {
		int k;
		cin >> k;
		vector<int> v(k);
		for (auto &it : v) {
			cin >> it;
			--it;
		}
		
		int u = v[0];
		for (auto it : v) if (d[u] < d[it]) u = it;
		for (auto &it : v) {
			if (it == u) continue;
			if (p[it] != -1) it = p[it];
		}
		bool ok = true;
		for (auto it : v) ok &= isAnc(it, u);
		if (ok) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const long long INF64 = 1e18;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for (auto &it : a) cin >> it;
	
	sort(a.begin(), a.end());
	vector<pair<int, int>> cnt;
	for (auto it : a) {
		if (cnt.empty() || cnt.back().first != it) {
			cnt.push_back({it, 1});
		} else {
			++cnt.back().second;
		}
	}
	vector<long long> prefsum, sufsum;
	vector<int> prefcnt, sufcnt; 
	for (int i = 0; i < int(cnt.size()); ++i) {
		long long cursum = cnt[i].first * 1ll * cnt[i].second;
		int curcnt = cnt[i].second;
		if (prefsum.empty()) {
			prefsum.push_back(cursum);
			prefcnt.push_back(curcnt);
		} else {
			prefsum.push_back(prefsum.back() + cursum);
			prefcnt.push_back(prefcnt.back() + curcnt);
		}
	}
	for (int i = int(cnt.size()) - 1; i >= 0; --i) {
		long long cursum = cnt[i].first * 1ll * cnt[i].second;
		int curcnt = cnt[i].second;
		if (sufsum.empty()) {
			sufsum.push_back(cursum);
			sufcnt.push_back(curcnt);
		} else {
			sufsum.push_back(sufsum.back() + cursum);
			sufcnt.push_back(sufcnt.back() + curcnt);
		}
	}
	reverse(sufsum.begin(), sufsum.end());
	reverse(sufcnt.begin(), sufcnt.end());
	
	long long ans = INF64;
	for (int i = 0; i < int(cnt.size()); ++i) {
		int cur = max(0, k - cnt[i].second);
		
		int needl = 0;
		if (i > 0) needl = min(cur, prefcnt[i - 1]);
		int needr = max(0, cur - needl);
		long long res = 0;
		if (i > 0 && needl > 0) {
			res += prefcnt[i - 1] * 1ll * (cnt[i].first - 1) - prefsum[i - 1];
			res += needl;
		}
		if (i + 1 < int(cnt.size()) && needr > 0) {
			res += sufsum[i + 1] - sufcnt[i + 1] * 1ll * (cnt[i].first + 1);
			res += needr;
		}
		ans = min(ans, res);
		
		needr = 0;
		if (i + 1 < int(cnt.size())) needr = min(cur, sufcnt[i + 1]);
		needl = max(0, cur - needr);
		res = 0;
		if (i > 0 && needl > 0) {
			res += prefcnt[i - 1] * 1ll * (cnt[i].first - 1) - prefsum[i - 1];
			res += needl;
		}
		if (i + 1 < int(cnt.size()) && needr > 0) {
			res += sufsum[i + 1] - sufcnt[i + 1] * 1ll * (cnt[i].first + 1);
			res += needr;
		}
		ans = min(ans, res);
	}
	
	cout << ans << endl;
	
	return 0;
}