fun main() {
    repeat(readLine()!!.toInt()) {
        when (val n = readLine()!!.toInt()) {
            in 0..999 -> println(n)
            in 1000..999_499 -> println("${(n + 500) / 1000}K")
            else -> println("${(n + 500_000) / 1_000_000}M")
        }
    }
}

fun main() {
    class M(val a: Int, val b: Int)
    repeat(readLine()!!.toInt()) {
        val n = readLine()!!.toInt()
        val ms = Array(n) {
            readLine()!!.split(" ").map { it.toInt() }.let { (a, b) -> M(a, b) }
        }
        var ans = -1
        fun check(x: Int) {
            if (ms.count { m -> x in m.a..m.b } == 1) ans = x
        }
        for (m in ms) {
            for (d in -1..1) {
                check(m.a + d)
                check(m.b + d)
            }
        }
        println(ans)
    }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val n = readLine()!!.toInt()
        val a = readLine()!!.split(" ").map { it.toInt() }
        val s = a.withIndex().sortedByDescending { it.value }
        val i = s.indexOfLast { it.value > 0 }
        val j = s.indexOfFirst { it.value < 0 }
        val c = CharArray(n) { '0' }
        for (k in 0 until i) c[s[k].index] = '1'
        if (j >= 0 && -s[j].value < s[i].value) {
            c[s[i].index] = '1'
            c[s[j].index] = '1'
        }
        val sum = s.sumBy { if (c[it.index] == '1') it.value else 0 }
        println(sum)
        println(c.joinToString(""))
    }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val (n, k) = readLine()!!.split(" ").map { it.toInt() }
        val a = readLine()!!.split(" ").map { it.toInt() }
        val s = a.withIndex().sortedByDescending { it.value }
        val d = IntArray(n)
        var rem = k
        for (p in 1 until n) {
            val i = s[p - 1].index
            val j = s[p].index
            d[j] = minOf(a[i] + d[i] - a[j] - 1, rem)
            rem -= d[j]
        }
        val add = rem / n
        val ext = rem % n
        for (p in 0 until n) d[s[p].index] += add + if (p < ext) 1 else 0
        println(d.joinToString(" "))
    }
}

fun main() {
    repeat(readLine()!!.toInt()) {
//        readLine() // skip empty line
        solveCase()
    }
}

private fun solveCase() {
    val (n, k) = readLine()!!.split(" ").map { it.toInt() }
    val gf = IntArray(n) { -1 }
    val gy = IntArray(2 * n)
    val gn = IntArray(2 * n)
    var ec = 0
    fun edge(x: Int, y: Int) {
        gy[ec] = y
        gn[ec] = gf[x]
        gf[x] = ec++
    }
    repeat(n - 1) {
        val (x, y) = readLine()!!.split(" ").map { it.toInt() - 1 }
        edge(x, y)
        edge(y, x)
    }
    val v = BooleanArray(n)
    val q = IntArray(n)
    var h = 0
    var t = 0
    fun enqueue(x: Int) {
        q[t++] = x
        v[x] = true
    }
    enqueue(0)
    var lc = 1
    while (lc < k && h < t) {
        val x = q[h++]
        var i = gf[x]
        var cc = 0
        while (i >= 0 && lc < k) {
            val y = gy[i]
            if (!v[y]) {
                enqueue(y)
                if (cc++ > 0) lc++
            }
            i = gn[i]
        }
        if (x == 0 && cc == 1) lc++
    }
    if (lc < k) {
        println("No")
        return
    }
    println("Yes")
    println(v.count { it })
    println(v.withIndex().filter { it.value }.joinToString(" ") { (it.index + 1).toString() })
}

import java.util.*

fun main() {
    repeat(readLine()!!.toInt()) {
//        readLine() // skip empty line
        solveCase()
    }
}

private data class Mv(val i: Int, val a: Int, val b: Int, var t: Int = 0) : Comparable<Mv> {
    override fun compareTo(other: Mv): Int = if (b != other.b) b.compareTo(other.b) else i.compareTo(other.i)
}

private fun solveCase() {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    val d = Array(n) { i ->
        readLine()!!.split(" ").map { it.toInt() }.let { (a, b) -> Mv(i, a, b) }
    }
    d.sortBy { it.a }
    var t = 0
    val w = TreeSet<Mv>()
    fun advance(to: Int) {
        while (t < to && !w.isEmpty()) {
            repeat(minOf(w.size, m)) {
                val v = w.first()
                v.t = t
                w -= v
            }
            t++
        }
        t = to
    }
    for (v in d) {
        advance(v.a)
        w += v
    }
    advance(Int.MAX_VALUE)
    d.sortBy { it.i }
    println(maxOf(0, d.map { it.t - it.b }.max()!!))
    println(d.joinToString(" ") { it.t.toString() })
}

fun main() {
    val (m, k) = readLine()!!.split(" ").map { it.toInt() }
    val f = factor(m) ?: run {
        println(-1)
        return
    }
    val dp = HashMap<Long,Long>()
    val dig = IntArray(100_000)
    fun count(nd: Int, p: Long = -1): Long {
        val e = f[0] + (f[1] shl 5) + (f[2] shl 10) + (f[3] shl 15) + (nd.toLong() shl 20)
        if (nd == 0) return if (e == 0L) 1 else 0
        if (p == -1L) dp[e]?.let { return it }
        var cnt = 0L
        for (d in 1..9) {
            dig[nd - 1] = d
            val df = factors[d]
            for (i in 0..3) f[i] -= df[i]
            if (f.all { it >= 0 }) {
                val nc = count(nd - 1)
                if (p >= 0 && cnt + nc > p) return count(nd - 1, p - cnt)
                cnt += nc
            }
            for (i in 0..3) f[i] += df[i]
        }
        dp[e] = cnt
        return cnt
    }
    var num = 1L
    var nd = 1
    while (count(nd) <= k - num) num += count(nd++)
    check(count(nd, k - num) == 1L)
    println(dig.take(nd).reversed().joinToString(""))
}

private val pr = listOf(2, 3, 5, 7)
private val factors = Array(10) { factor(it)!! }

private fun factor(m: Int): IntArray? {
    val f = IntArray(4)
    if (m <= 1) return f
    var rem = m
    for ((i, p) in pr.withIndex()) {
        while (rem % p == 0) {
            rem /= p
            f[i]++
        }
    }
    return f.takeIf { rem == 1 }
}

fun main() {
    class Ans(val a: String, val m: String)
    repeat(readLine()!!.toInt()) {
        val s = readLine()!!
        val n = s.length
        val dp = Array(n) { i -> arrayOfNulls<Ans>(i + 1) }
        dp[0][0] = Ans(s.substring(0, 1), "R")
        var best = Ans(s, "")
        fun updateBest(p: Ans) {
            if (p.a <= best.a) best = p
        }
        fun updateDP(i: Int, j: Int, p: Ans) {
            val cur = dp[i][j]
            if (cur == null || p.a < cur.a) dp[i][j] = p
        }
        for (i in 1 until n) {
            for (j in 0 until i) {
                val p = dp[i - 1][j] ?: continue
                updateDP(i, j, Ans(p.a + s[i], p.m + "R"))
                if (j >= i - j) continue
                if (s[i] == p.a[j]) updateDP(i, j + 1, Ans(p.a, p.m + "B"))
                if (s[i] < p.a[j]) updateBest(Ans(p.a, p.m + "B".repeat(n - i)))
            }
        }
        for (p in dp[n - 1]) if (p != null) updateBest(p)
        println(best.m)
    }
}

import java.util.*

private class Block(val l: Int, val r: Int) : Comparable<Block> {
    fun cover(c: Block) = l <= c.l && r >= c.r
    override fun compareTo(other: Block): Int = l.compareTo(other.l)
}

fun main() {
    val (n, d) = readLine()!!.split(" ").map { it.toInt() }
    val bh = arrayOfNulls<TreeSet<Block>>(n + 1) // blocks by height
    // Segment tree
    val tt = BooleanArray(4 * d) // terminal(leaf) node in segment tree
    val th = IntArray(4 * d) // max height in this segment
    tt[0] = true
    // Segment tree functions
    fun findMax(b: Block, i: Int, tl: Int, tr: Int): Int {
        if (tt[i] || b.l <= tl && b.r >= tr) return th[i]
        val tm = (tl + tr) / 2
        return maxOf(
            if (b.l <= tm) findMax(b, 2 * i + 1, tl, tm) else 0,
            if (b.r > tm) findMax(b, 2 * i + 2, tm + 1, tr) else 0
        )
    }
    fun setLeaf(i: Int, h: Int) {
        tt[i] = true
        th[i] = h
    }
    fun place(b: Block, h: Int, i: Int, tl: Int, tr: Int) {
        if (b.l <= tl && b.r >= tr) return setLeaf(i, h)
        val tm = (tl + tr) / 2
        val j1 = 2 * i + 1
        val j2 = 2 * i + 2
        if (tt[i]) { // split node
            tt[i] = false
            setLeaf(j1, th[i])
            setLeaf(j2, th[i])
        }
        if (b.l <= tm) place(b, h, j1, tl, tm)
        if (b.r > tm) place(b, h, j2, tm + 1, tr)
        th[i] = maxOf(th[j1], th[j2])
    }
    // Simulate each incoming block & print answer
    var bc = 0
    repeat(n) {
        val b = readLine()!!.split(" ").map { it.toInt() }.let{ (l, r) -> Block(l, r) }
        var maxH = findMax(b, 0, 1, d)
        while (true) {
            val bs = bh[maxH] ?: break
            var floor = bs.floor(b)
            if (floor != null && floor.r < b.l) floor = bs.higher(floor)
            if (floor == null) floor = bs.first()
            check(floor.l <= b.r)
            val list = bs.tailSet(floor).takeWhile { it.l <= b.r }
            if (!b.cover(list.first()) || !b.cover(list.last())) break
            for (c in list) bs -= c // don't use bs.removeAll(list)
            bc -= list.size
            maxH--
        }
        val h = maxH + 1
        place(b, h, 0, 1, d)
        val bs = bh[h] ?: run { TreeSet<Block>().also { bh[h] = it } }
        bs += b
        println(++bc)
    }
}

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

int c, l, v0, v1, a;

inline bool read() {
	if(!(cin >> c >> v0 >> v1 >> a >> l))
		return false;
	
	return true;
}

inline void solve() {
	int pos = v0;
	int t = 1;
	
	int add = v0;
	
	while(pos < c) {
		add = min(v1, add + a);
		
		pos += add - l;
		t++;
	}
	
	cout << t << endl;
}

int n, a;

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

inline void solve() {
	int base = n * a / 180;
	base = max(1, min(n - 2, base));
	
	int bk = base;
	for(int ck = max(1, base - 2); ck <= min(n - 2, base + 2); ck++) {
		if(abs(180 * ck - n * a) < abs(180 * bk - n * a))
			bk = ck;
	}
	
	cout << 2 << " " << 1 << " " << bk + 2 << endl;
}

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

typedef long long li;

const int N = 1000 * 1000 + 555;

int n, p[N];

inline bool read() {
	if(!(cin >> n))
		return false;
	forn(i, n)
		assert(scanf("%d", &p[i]) == 1);
	return true;
}

li sum[N], df[N], res[N];

inline void add(int lf, int rg, int k, int b) {
	if(lf > rg)
		return;
				
	sum[lf] += b;
	df[lf] += k;
	
	sum[rg + 1] -= b + k * 1ll * (rg - lf);
	df[rg] -= k;
}

inline void calc() {
	li curdf = 0;
	forn(i, n) {
		sum[i] += curdf;
		curdf += df[i];
	}
	
	li cursm = 0;
	forn(i, n) {	
		cursm += sum[i];
		res[i] += cursm;
	}
}

inline void solve() {
	memset(sum, 0, sizeof sum);
	memset(df, 0, sizeof df);
	memset(res, 0, sizeof res);
	
	forn(i, n) {
		int c1 = i + 1, p1 = 0;
		int c2 = n,     p2 = p1 + c2 - c1;
		int c3 = i,     p3 = p2 + c3;
		
		if(p[i] <= c3) {
			add(p1, p2, 1, c1 - p[i]);
			add(p2 + 1, p2 + p[i], -1, p[i] - 1);
			add(p2 + p[i] + 1, p3, 1, 1);
		} else {
			add(p1, p1 + p[i] - c1, -1, p[i] - c1);
			add(p1 + p[i] - c1 + 1, p2, 1, 1);
			add(p2 + 1, p3, -1, p[i] - 1);
		}
	}
	
	calc();
	
	int ans = 0;
	forn(i, n)
		if(res[ans] > res[i])
			ans = i;
			
	cout << res[ans] << " " << ans << endl;
}

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

#define all(a) (a).begin(), (a).end()
#define sqr(a) ((a) * (a))
#define sz(a) int(a.size())
#define mp make_pair
#define pb push_back

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

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

int n[3], m[3], s[3];

inline bool read() {
	if(scanf("%d %d %d", &n[0], &n[1], &n[2]) != 3)
		return false;
	forn(i, 3)
		assert(scanf("%d", &m[i]) == 1);
	forn(i, 3)
		assert(scanf("%d", &s[i]) == 1);
	return true;
}

const int N = 2 * 1000 * 1000 + 55;
int ls[N];

inline void precalc() {
	memset(ls, -1, sizeof ls);
	
	ls[0] = ls[1] = 1;
	fore(i, 2, N) {
		if(ls[i] != -1)
			continue;
			
		ls[i] = i;
		for(li j = i * 1ll * i; j < N; j += i)
			if(ls[j] == -1)
				ls[j] = i;
	}
}

inline vector<pt> fact(int n[3]) {
	vector<int> divs;
	
	forn(i, 3) {
		int cur = n[i];
		while(ls[cur] != cur) {
			divs.pb(ls[cur]);
			cur /= ls[cur];
		}
		if(cur > 1)
			divs.pb(cur);
	}
	
	sort(all(divs));
	vector<pt> ans;
	
	int u = 0;
	while(u < sz(divs)) {
		int v = u;
		while(v < sz(divs) && divs[v] == divs[u])
			v++;
		
		ans.pb(mp(divs[u], v - u));
		u = v;
	}
	
	return ans;
}

li ans;

li nn, mm, ss;
vector<pt> fs;
vector<li> bad;

void calcDivs(int pos, li val) {
	if(pos >= sz(fs)) {
		ans += (val <= nn);
		return;
	}
	
	li cv = 1;
	forn(i, fs[pos].y + 1) {
		calcDivs(pos + 1, val * cv);
		
		cv *= fs[pos].x;
	}
}

void calcInEx(int pos, li val, int cnt) {
	if(pos >= sz(bad)) {
		li k = cnt ? -1 : 1;
		
		ans += k * (mm / val);
		return;
	}
	
	calcInEx(pos + 1, val, cnt);
	calcInEx(pos + 1, val * bad[pos], cnt ^ 1);
}

inline void solve() {
	ans = 0;
	s[0] *= 2;
	
	nn = n[0] * 1ll * n[1] * 1ll * n[2];
	mm = m[0] * 1ll * m[1] * 1ll * m[2];
	ss = s[0] * 1ll * s[1] * 1ll * s[2];
	
	fs = fact(s);
	calcDivs(0, 1);
	
	bad.clear();
	vector<pt> fn = fact(n);
	
	forn(i, sz(fn)) {
		li cv = fn[i].x;
		forn(k, fn[i].y) {
			if(ss % cv != 0) {
				bad.pb(cv);
				break;
			}
			cv *= fn[i].x;
		}
	}
	
	calcInEx(0, 1, 0);
	
	printf("%I64d\n", ans);
}

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

#define all(a) (a).begin(), (a).end()
#define sqr(a) ((a) * (a))
#define sz(a) int(a.size())
#define mp make_pair
#define pb push_back

#define x first
#define y second

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

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

int gcd(int a, int b) {
	if(a == 0)
		return b;
	return gcd(b % a, a);
}

int exgcd(int a, li &x, int b, li &y) {
	if(a == 0) {
		x = 0, y = 1;
		return b;
	}
	
	li xx, yy;
	int g = exgcd(b % a, xx, a, yy);
	
	x = yy - b / a * xx;
	y = xx;
	
	return g;
}

const int N = 200 * 1000 + 555;
int t, n, a[N];

inline bool read() {
	if(!(cin >> t >> n))
	    return false;
	forn(i, n)
		assert(scanf("%d", &a[i]) == 1);
	return true;
}

int pf[N], s;

inline li up(li a, li b) {
	return (a + b - 1) / b;
}

inline int findPos(int a, int b, int c) {
	li x, y;
	int g = exgcd(a, x, b, y);
	assert(c % g == 0);
	
	x *= +c / g;
	y *= -c / g;
	assert(a * 1ll * x - b * 1ll * y == c);
	
	int ag = a / g;
	int bg = b / g;
	
	li k = 0;
	if(x < 0)
		k = up(-x, bg);
	if(x >= bg)
		k = -up(x - bg, bg);	
	x += bg * k;
	y += ag * k;
		
	assert(0 <= x && x < bg);
	
	k = 0;
	if(y < 0)
		k = up(-y, ag);
	x += bg * k;
	y += ag * k;

	return x;
}

map< int, set<pt> > cycle;

int ans[N];

inline void solve() {
	cycle.clear();
	pf[0] = 0;
	fore(i, 1, n)
		pf[i] = (pf[i - 1] + a[i]) % t;
	
	s = (a[0] + pf[n - 1]) % t;
	int g = gcd(s, t);
	
	forn(i, n) {
		int st = pf[i] % g;
		auto& cc = cycle[st];
		
		int pos = findPos(s, t, pf[i] - st);
		
		if(cc.empty()) {
			ans[i] += t / g;
			cc.insert(pt(pos, -i));
		} else {
			auto rg = cc.lower_bound(pt(pos, -i));
			if(rg == cc.end()) {
				ans[i] += t / g - pos;
				rg = cc.begin();
				ans[i] += rg->x;
			} else
				ans[i] += rg->x - pos;
				
			auto lf = cc.lower_bound(pt(pos, -i));
			if(lf == cc.begin())
				lf = --cc.end();
			else
				lf--;
			ans[ -(lf->y) ] -= ans[i];
			
			cc.insert(pt(pos, -i));
		} 
	}
	
	forn(i, n)
		printf("%d ", ans[i]);
	puts("");
}

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;
template<typename T>
using pair2 = pair<T, T>;

#ifdef WIN32
    #define LLD "%I64d"
#else
    #define LLD "%lld"
#endif

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

const int maxn = 305;

int pair3[maxn];
int n;
vector<vector<int>> answer;

void add3(int a, int b, int c)
{
    answer.pb({a, b, c});
}

void add4(int a, int b, int c, int d)
{
    answer.pb({a, b, c, d});
}

int main()
{
    cin >> n;
    if (n % 2 == 0)
    {
        pair3[0] = 3; // 0 1 3
        pair3[2] = 1; // 2 3 1
        add3(0, 1, 2);
        add3(2, 3, 0);
        for (int i = 4; i < n; i += 2)
        {
            add4(0, pair3[0], 1, i);
            add3(i, i + 1, 0);
            pair3[i] = 1;
            pair3[0] = i + 1;
            for (int j = 2; j < i; j += 2)
            {
                add4(j, pair3[j], j + 1, i);
                add4(j, i, j + 1, i + 1);
                pair3[j] = i + 1;
            }
        }
        for (int i = 0; i < n; i += 2)
        {
            add3(i, i + 1, pair3[i]);
        }
    } else
    {
        pair3[1] = 0; // 1 2 0
        add3(0, 1, 2);
        for (int i = 3; i < n; i += 2)
        {
            add3(i, i + 1, 0);
            pair3[i] = 0;
            for (int j = 1; j < i; j += 2)
            {
                add4(j, pair3[j], j + 1, i);
                add4(j, i, j + 1, i + 1);
                pair3[j] = i + 1;
            }
        }
        for (int i = 1; i < n; i += 2)
        {
            add3(i, i + 1, pair3[i]);
        }
    }
    printf("%d\n", (int)answer.size());
    for (auto &t : answer)
    {
        printf("%d", (int)t.size());
        for (auto t2 : t) printf(" %d", t2 + 1);
        printf("\n");
    }
    return 0;
}