Subset Multiplication

The key is to stop trying to recover the whole hidden array. That is a trap. We only need some valid $x$, and the adjacent pairs tell us exactly which prime factors $x$ is forced to contain.

Suppose Bob either leaves position $i$ alone or multiplies it by $x$. Write

$$b_i = a_i \cdot c_i$$

where $c_i$ is either $1$ or $x$.

The original array is beautiful, so

$$a_i \mid a_{i+1}$$

for every adjacent pair.

Now inspect what happens to divisibility in $b$.

For a pair $(i,i+1)$, there are four cases:

• neither element was multiplied: $b_i=a_i$, $b_{i+1}=a_{i+1}$, so $b_i \mid b_{i+1}$;
• only the right element was multiplied: $b_i=a_i$, $b_{i+1}=a_{i+1}x$, so $b_i \mid b_{i+1}$;
• both were multiplied: $b_i=a_ix$, $b_{i+1}=a_{i+1}x$, so $b_i \mid b_{i+1}$;
• only the left element was multiplied: $b_i=a_ix$, $b_{i+1}=a_{i+1}$, and divisibility may break.

So a broken pair, meaning

$$b_i \nmid b_{i+1},$$

can only come from the last case: the left element was multiplied by $x$, and the right one was not.

That means the original left value was

$$a_i = \frac{b_i}{x},$$

and we need

$$\frac{b_i}{x} \mid b_{i+1}.$$

So what must $x$ contain?

Let

$$g = \gcd(b_i,b_{i+1}).$$

The common part $g$ is already shared between the two numbers. The leftover part of $b_i$ that $b_{i+1}$ does not contain is

$$\frac{b_i}{g}.$$

For $\frac{b_i}{x}$ to divide $b_{i+1}$, $x$ has to remove at least that leftover part from $b_i$. Therefore every bad pair forces

$$\frac{b_i}{\gcd(b_i,b_{i+1})} \mid x.$$

So the smallest number satisfying all forced requirements is

$$\operatorname{lcm}\left(\frac{b_i}{\gcd(b_i,b_{i+1})}\right)$$

over all indices where $b_i \nmid b_{i+1}$.

If there are no bad pairs, then $b$ is already beautiful, so $x=1$ works. Bob could have multiplied nothing. Very dramatic sabotage, truly.

Why this LCM is actually valid

Let the answer we compute be $y$.

For every bad pair, $y$ is divisible by

$$d_i=\frac{b_i}{\gcd(b_i,b_{i+1})}.$$

Now construct an array $a$ like this:

• if $y \mid b_i$, set $a_i=\frac{b_i}{y}$;
• otherwise, set $a_i=b_i$.

This corresponds to saying Bob multiplied exactly the positions divisible by $y$.

We need to check $a_i \mid a_{i+1}$ for every adjacent pair.

If $b_i \mid b_{i+1}$, then this pair is already fine. Dividing either both values by $y$, or just the right value by $y$, cannot break the divisibility. The only suspicious subcase would be dividing the left but not the right, but if $y \mid b_i$ and $b_i \mid b_{i+1}$, then $y \mid b_{i+1}$ too, so both get divided.

If $b_i \nmid b_{i+1}$, then $d_i \mid y$. Also, for any valid hidden solution, the real $x$ must divide $b_i$ on such a bad pair, and $d_i \mid x$, so the computed $y$, being an LCM of such forced divisors, divides some valid $x$. Since that valid $x$ divides $b_i$, $y$ divides $b_i$ too. Thus the left side gets divided by $y$.

Now we need

$$\frac{b_i}{y} \mid b_{i+1}.$$

Because $d_i = b_i/g$ divides $y$, dividing $b_i$ by $y$ removes at least all the prime-power excess that prevented $b_i$ from dividing $b_{i+1}$. So the repaired left value divides $b_{i+1}$. If the right side also gets divided by $y$, that would only happen when $y \mid b_{i+1}$; then the divisibility still holds after dividing both by the same number.

So $y$ works.

Algorithm

For each test case:

1. Start with ans = 1.
2. For every adjacent pair $(b_i,b_{i+1})$:
   • if $b_{i+1} \bmod b_i = 0$, ignore it;
   • otherwise compute $d=\frac{b_i}{\gcd(b_i,b_{i+1})}$;
   • set ans = lcm(ans, d).
3. Output ans.

Use 64-bit integers while computing the LCM. The final answer is guaranteed to fit the required constraints because the statement guarantees that a valid answer exists.

Complexity:

$$O(n \log V)$$

per test case from the gcd calls, where $V \le 10^9$. Across all tests, this is easily fine for $\sum n \le 6\cdot 10^5$.