令 $b_i=\gcd(a_1,a_2,\cdots,a_3)$， 不难发现 $b_{i+1}\mid b_i$。

于是我们设 $f_x$ 为将序列 $a$ 中所有 $x$ 的倍数重排得到序列 $t_1,t_2,\cdots,t_m$ 之后，$\sum_{i=1}^m\gcd(t_1,t_2,\cdots,t_i)$ 的最大值。

那么显然 $f$ 在 $x$ 处的值只会从它的所有倍数 $kx$ 处转移而来，并且 $f_{kx}$ 对应的最优的序列一定是 $f_x$ 对应的最优的序列的前缀。

转移方程为

$$\displaylines{f_x=\max_{kx\le\max\{a\}}\left\{f_{kx}+\sum_{i=1}^n[x\mid a_i\land kx\not\mid a_i]\right\} }$$

这样转移是 $O(n\log n)$ 的。

考虑到对于合数 $k=pq$（$p,q$ 不为 $1$），$f_{kx}\to f_{px}\to f_{qx}$ 的转移不比 $f_{kx}\to f_{x}$ 劣，所以实际上可以仅枚举所有质数 $k$ 进行转移。

对每条线 DP，从上往下安排折线形态。

因为前一条线对当前的线有限制，所以需要计入状态。即状态应与已分配过的线数 $n$、当前线已安排的行数 $i$、左侧第一条线的形态 $T$，当前线已安排的形态 $S$ 有关。

---

发现状态中存在一些冗余信息：

我们不关心上一条折线 $T$ 第 $i$ 行以上的走势，只关心当前线 $S$ 到 $T$ 在第 $i$ 行上之间的宽度。

---

再次深入考虑后我们发现 $T$ 的第 $i$ 行一下的某一部分我们也不关心。

如果，我们安排当前线以下部分一直向左直到撞到上一条线，至少一直向左的部分长为 $k$，那么折线 $T$ 的第 $i$ 行一下的 $k$ 段，其形态我们也不关心。

---

又想到 $S$ 的长度仅为 $i$，$T$ 中我们只关心 $i$ 以下一直向左走多久会被撞到，和撞到的位置以下 $T$ 的形态，我们可以巧妙地设置状态。

这个状态的意义为，第 $i$ 行及以上部分为当前安排的折线形态 $S$，以下为尽量往左走，能够走出的形态。

这样将复杂度优化到 $O(n^22^n)$。

期望 DP，只维护合法的状态。

每次询问暴力做矩阵快速幂会超时，所幸，对于所有询问，要做快速幂的矩阵是相同的，并且我们只需要向量乘矩阵幂后的结果。所以可以预处理出快速幂所需要的中间量，即 $A^{2^k}$ 处的取值，快速幂就只需 $\log n$ 次向量乘矩阵，时间开销由 $O(Tm^3\log n)$ 优化为 $O(m^3\log n+Tm^2\log n)$。