Let the answers be \(R_1, R_2, \dots, R_N\). For convenience, let \(R_0 = 0\). An observation using dynamic programming reveals that \(R_1, R_2, \dots, R_N\) can be calculated using the following formula:

\[R_i = 2R_{i - 1} + \sum_{j=1}^{i-1} 2^j \gcd(A_i, A_j).\]

If we compute \(R\) directly using this formula, it would take \(\mathrm{O}(N^2 \log \max(A))\) time, so we need to optimize it.

In fact, we can speed up the calculation by using the Euler’s totient function \(\varphi(n)\). The totient function satisfies the following property (where \(d \vert n\) denotes that \(d\) devides \(n\)):

• \(\sum_{d \vert n} \varphi(d) = n\) holds for all positive integers \(n\).

Using the totient function, we can perform the following transformations (here, \([ \text{cond} ]\) is a function that takes the value \(1\) if \(\text{cond}\) is true, and \(0\) otherwise):

\[ \begin{aligned} \gcd(n, m) &= \sum_{d \vert \gcd(n, m)} \varphi(d) \\ &= \sum_{d \vert n, d \vert m} \varphi(d) \\ &= \sum_{d \vert n} \varphi(d) [d \vert m] \end{aligned} \]

\[ \begin{aligned} &\sum_{j=1}^{i-1} 2^j \gcd(A_i, A_j) \\ &= \sum_{j=1}^{i-1} 2^j \sum_{d \vert A_i} \varphi(d) [d \vert A_j] \\ &= \sum_{d \vert A_i} \varphi(d) \sum_{j=1}^{i-1} 2^j [d \vert A_j] \end{aligned} \]

By using this formula, we can derive a DP to compute \(R_1, R_2, \dots, R_N\) in \(\mathrm{O}(\max(A) + \sum_{i=1}^N d(A_i))\) time (where \(d(n)\) denotes the number of divisors of \(n\)). Specifically, proceed as follows:

• Initialize an array \(s = (s_1, s_2, \dots, s_{\max(A)})\) with zeros.
• For \(i = 1, 2, \dots, N\), perform the following:
  • Set \(R_i = 2 \times R_{i-1} + \sum_{d \vert A_i} \varphi(d) s_d\).
  • Then, for each \(d\) dividing \(A_i\), add \(2^i\) to \(s_d\).

In this DP, we need to enumerate the divisors for each of \(1, 2, \dots, \max(A)\) and compute \(\varphi(1), \varphi(2), \dots, \varphi(\max(A))\) in advance. Both can be precomputed in about \(\mathrm{O}(\max(A) \log \max(A))\) time.

Therefore, we can solve this problem in \(\mathrm{O}(\max(A) \log \max(A) + \sum_{i=1}^N d(A_i))\) time. Considering that \(d(A_i) \leq 128\) under the constraints, this runs sufficiently fast.