Do we really need to reorder more than once?

Any subtraction done after a reorder could have been done before it instead.
So optimal strategy is: subtract some elements, then reorder at most once.

Compute cost without reordering — check if $$$a_i \geq b_i$$$ for all $$$i$$$. Cost = $$$\sum (a_i - b_i)$$$.

Compute cost with reordering — sort both arrays. Pair largest $$$a_i$$$ with largest $$$b_i$$$, and so on.
Check feasibility. Cost = $$$c + \sum (a_i - b_i)$$$.

Why this pairing? If the largest $$$b_i$$$ is 20, at least one $$$a_i$$$ must be $$$\geq 20$$$. If the second largest is 10, at least two $$$a_i$$$ must be $$$\geq 10$$$, etc.

Answer is $$$\min$$$ of both costs. If both are impossible, output $$$-1$$$.

Try to simplify the identity $$$\gcd(\text{lcm}(a,b),\, \text{lcm}(b,c)) = \gcd(a,c)$$$.

Look at a single prime $$$p$$$. Let its powers in $$$a, b, c$$$ be $$$i, j, k$$$ respectively.
LCM takes max power, GCD takes min power. The identity becomes:

Left side simplifies to $$$\max(j,\, \min(i,k))$$$.
So the equation holds iff $$$j \leq \min(i, k)$$$.

$$$j \leq \min(i,k)$$$ for every prime $$$p$$$ means $$$b \mid a$$$ and $$$b \mid c$$$.

Triple $$$(a, b, c)$$$ is crimson iff $$$b \mid a$$$ and $$$b \mid c$$$.
For a fixed $$$b$$$, both $$$a$$$ and $$$c$$$ can be any of the $$$\lfloor n/b \rfloor$$$ multiples of $$$b$$$ up to $$$n$$$.

A guild $$$(v, h)$$$ is the set of nodes in the subtree of $$$v$$$ at distance exactly $$$h$$$ from $$$v$$$.
When is guild $$$(u, d)$$$ the same set as guild $$$(\text{child}, d-1)$$$?

If only one child's subtree has nodes at distance $$$d$$$ from $$$u$$$, then $$$(u, d)$$$ gives the same set as (that child, $$$d-1$$$). No new guild!

If at least two children have nodes at distance $$$d$$$ from $$$u$$$, no single descendant can reproduce the combined set. This is a new guild unique to $$$u$$$.

For each node $$$u$$$, let child subtree depths (max distance reachable from $$$u$$$ through each child) be $$$d_1 \geq d_2 \geq \ldots$$$

Guild $$$(u, d)$$$ is unique to $$$u$$$ for $$$d = 0, 1, \ldots, d_2$$$ — contributing $$$d_2 + 1$$$ guilds.
If fewer than 2 children, only $$$d = 0$$$ is unique — contributes 1.

Run a single DFS. For each node, sort child depths descending.
- If $$$\geq 2$$$ children: add $$$d_2 + 1$$$ to answer.
- Else: add 1.

Return $$$d_1 + 1$$$ to the parent. $$$O(n)$$$ per test case.

How many layers does $$$n = p^k$$$ require?
Divisors are $$$p, p^2, \ldots, p^k$$$. Each divides the next, so they must go in strictly increasing layers — exactly $$$k$$$ layers.

For $$$n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_r^{e_r}$$$, we need at least $$$e_1 + e_2 + \cdots + e_r$$$ layers (= powerSum).
Each step up in exponent sum forces a new layer.

The $$$r$$$ primes $$$p_1, \ldots, p_r$$$ are pairwise coprime, so no two can share a layer. They each need a dedicated layer.
For divisors with exponent sum $$$ \gt 1$$$, all of them can share one layer — arrange in a chain where adjacent numbers share a prime factor.

Total layers = $$$r$$$ layers for primes + one layer per remaining exponent sum level.

Use a linear sieve for $$$O(\log n)$$$ factorization per query.

Assume the final string is fixed (all N already replaced). How do we count mistakes?

Chell picks a segment $$$[l, r]$$$ and declares everything inside fake, everything outside real.
Mistakes = missed fakes + wrong reals
= F's outside $$$[l,r]$$$ + T's inside $$$[l,r]$$$

Now decompose missed fakes:
F's outside $$$[l,r]$$$ = total F's $$$-$$$ F's inside $$$[l,r]$$$

So: Mistakes = total F's $$$-$$$ F's inside $$$[l,r]$$$ + T's inside $$$[l,r]$$$

Now change F $$$\to +1$$$, T $$$\to -1$$$. Then:
- F's inside $$$[l,r]$$$ contribute $$$+1$$$ each to $$$\text{sum}(s[l..r])$$$
- T's inside $$$[l,r]$$$ contribute $$$-1$$$ each to $$$\text{sum}(s[l..r])$$$

So $$$\text{F's inside} - \text{T's inside} = \text{sum}(s[l..r])$$$, which gives:

Since $$$F_{cnt}$$$ is fixed for a given string, Chell minimizes mistakes by choosing $$$[l,r]$$$ to maximize $$$\text{sum}(s[l..r])$$$.

This is exactly the maximum subarray sum, solvable in $$$O(n)$$$ with Kadane's algorithm.

GLaDOS controls the N replacements and wants to maximize $$$F_{cnt} - \text{maxSubarraySum}$$$.
Kadane's algorithm tracks two values as it scans left to right:
$$$c$$$ — max subarray sum ending at current position (reset to 0 if negative).
$$$m$$$ — max subarray sum seen so far.
So we enumerate N-replacements while tracking $$$(f,\ m,\ c)$$$ where $$$f$$$ = no of F's placed so far.

$$$O(n^4)$$$ DP — 3D boolean state:
$$$dp[f][m][c]$$$ = True if tuple $$$(f, m, c)$$$ is reachable, False otherwise.
Initial state: $$$dp[0][0][0] = \text{True}$$$, all others False.

Transitions for each character (explore both branches when N):
Place T: $$$f' = f,\quad c' = \max(0,\ c-1),\quad m' = \max(m,\ c')$$$
Place F: $$$f' = f+1,\quad c' = c+1,\quad m' = \max(m,\ c')$$$

Answer $$$= \max$$$ over all reachable $$$(f, m, c)$$$ of $$$(f - m)$$$.
$$$O(n^3)$$$ states $$$\times$$$ $$$O(n)$$$ characters $$$= O(n^4)$$$ total.

$$$O(n^3)$$$ optimisation — remove $$$m$$$ from the state dimension:
For fixed $$$(f, c)$$$, the answer contribution is $$$f - m$$$. Since $$$f$$$ is fixed, we want to minimise $$$m$$$.
So instead of a 3D bool, store the minimum achievable $$$m$$$:
$$$dp[f][c]$$$ = min $$$m$$$ over all reachable N-replacements so far.
Initial state: $$$dp[0][0] = 0$$$, all others $$$= \infty$$$.

Transitions (both branches when N):
Place T: $$$f' = f,\quad c' = \max(0,\ c-1),\quad m' = \max(dp[f][c],\ c')$$$
$$$\quad\quad dp[f'][c'] = \min(dp[f'][c'],\ m')$$$
Place F: $$$f' = f+1,\quad c' = c+1,\quad m' = \max(dp[f][c],\ c')$$$
$$$\quad\quad dp[f'][c'] = \min(dp[f'][c'],\ m')$$$

After processing all characters:

$$$O(n^2)$$$ states $$$\times$$$ $$$O(n)$$$ characters $$$= O(n^3)$$$ total.