The idea is to try all values of the new element (from $$$1$$$ to $$$M$$$) and take the maximum LCM it gives you. Naively, this is $$$O(T(N + M)\log(M))$$$ (extra log because we need GCD for LCM), which passes fine. The issue is, the LCM could be huge, so we need to do it without overflowing.

Instead, let's represent the LCM as the prime factors that make it up, e.g. $$$12$$$ becomes $$$2 \cdot 2 \cdot 3$$$. Now consider each prime factor individually. In terms of each prime factor $$$p$$$, for each element in the array, the LCM must be big enough to be a multiple of all of them. Formally, if each array element is $$$p^k \cdot something$$$, then the LCM must be divisible by $$$p^m$$$, where $$$m$$$ is the maximum over all $$$k$$$ of all array elements. If we do this for each prime factor of the array elements, we'll have the LCM.

Now we handle the new element. Let's call it... $$$G$$$ (this is also how I come up with variable names). What does a candidate $$$G$$$ contribute to the LCM? Since the LCM is the product of $$$p^m$$$ for all valid $$$p$$$, we only care about the prime factors of $$$G$$$ where we can somehow increase some values of $$$m$$$. Specifically, for all prime factors $$$p$$$ of $$$G$$$, if $$$G$$$ is divisible by $$$p^k$$$ and the LCM is divisible by $$$p^m$$$, then we increase the LCM only if $$$k > m$$$, and we increase the LCM by $$$p^{k - m}$$$. So the final contribution is $$$\prod{p^{\max(0, k - m)}}$$$ for all prime factors $$$p$$$ of $$$G$$$.

Try this for all $$$G$$$ from $$$1$$$ to $$$M$$$, and you're done. This is, as an upper bound, still $$$O(T(N + M)\log(M))$$$ because each number can have around $$$log(M)$$$ prime factors, but it won't run close to this practically. To get this complexity, precompute prime factors for each number at the beginning (this can be done, say, in $$$O(10000\sqrt {10000})$$$).

The only issue with the solution above was that it didn't reset the max counts between test cases.

I appreciate you asking, because by explaining the problem, I've come to think of LCM in a different way.