#include<bits/stdc++.h>
using namespace std;
#include "spoj.h"

const int N = 1e5 + 9, MX = 1e9;

long long MIN(vector<int> a) {
  long long ans = 0;
  int n = a.size();
  vector<int> l(n), r(n);
  stack<pair<int, int>> s1, s2;
  for (int i = 0; i < n; ++i) {
    int cnt = 1; 
    while (!s1.empty() && s1.top().first > a[i]){
      cnt += s1.top().second;
      s1.pop();
    }
    s1.push({a[i], cnt});
    l[i] = cnt;
  }
  for (int i = n - 1; i >= 0; --i) {
    int cnt = 1;
    while (!s2.empty() && s2.top().first >= a[i]) {
      cnt += s2.top().second;
      s2.pop();
    }
    s2.push({a[i], cnt});
    r[i] = cnt;
  }
  for (int i = 0; i < n; ++i) {
    ans += 1LL * a[i] * l[i] * r[i];
  }
  return ans;
}
vector<int> d[N];
int f[N], last[N];
long long mul[N];
long long GCD(vector<int> a) {
  int n = a.size();
  long long ans = 0;
  int ok = 1;
  for (int i = 1; i < n; i++) {
    if (a[i] == 1 || a[i - 1] == 1 || __gcd(a[i], a[i - 1]) == 1) {

    }
    else {
      ok = 0;
      break;
    }
  }
  if (ok) {
    for (int i = 0; i < n; i++) {
      ans += a[i];
    }
    ans += 1LL * n * (n - 1) / 2;
    return ans;
  }
  memset(f, 0, sizeof f);
  memset(last, -1, sizeof last);
  memset(mul, 0, sizeof mul);
  int M = 0;
  for (int i = 0; i < n; i++) {
    M = max(M, a[i]);
  }
  for (int i = 0; i < n; i++) {
    for (auto x: d[a[i]]) {
      if (last[x] == i - 1) {
        mul[x] += f[x] + 1;
        ++f[x];
      }
      else {
        ++mul[x];
        f[x] = 1;
      }
      last[x] = i;
    }
  }
  for (int i = M; i >= 1; i--) {
    for (int j = i + i; j <= M; j += i) {
      mul[i] -= mul[j];
    }
    ans += mul[i] * i;
  }
  return ans;
}
int main() {
    spoj_init();
      for (int i = 1; i < N; i++) {
        for (int j = i; j < N; j += i) {
          d[j].push_back(i);
        }
      }
    int t; fscanf(spoj_p_in, "%d", &t);
    for (int tt = 1; tt <= t; tt++) {
        int D; fscanf(spoj_p_in, "%d", &D);
        int n;
        spoj_assert(fscanf(spoj_t_out, "%d", &n) == 1);
        spoj_assert(1 <= n && n <= 100000);
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            spoj_assert(fscanf(spoj_t_out, "%d", &a[i]) == 1);
            spoj_assert(1 <= a[i] && a[i] <= 100000);        
        }
        long long cur = MIN(a) - GCD(a);
        spoj_assert(cur == D);
    }
    char extra[100];
    spoj_assert(fscanf(spoj_t_out, "%s", extra) != 1);
    return 0;
}