#include "bits/stdc++.h"
using namespace std;
typedef long long int ll;
typedef pair < int , int > p;
#define rep(i,a,n)  for(int i = a; i < n; i++)
const int mod = 1000003;
const int N = 2e6+5;
int h[N] = {0}, sum[N] = {0};
 
void solve(){
    int n, i, num;int ele = 0;
    int ans(0);
    cin >> n;
 
    rep(i,0,n)cin >> num, h[num]++, sum[num]++;
    rep(i,1,N)sum[i] += sum[i-1];
    for(int i = 1; i < N; i++){
        if(h[i]){
        	ele = 0;
        	for(int j = i; j < N; j += i){
	            ans = (ans % mod + ((j / i) * 1LL * h[i] * h[j]) % mod) % mod;
	            if(i == j || i == 1)continue;
	           ans =(ans % mod + ( ((j-1) / i) * 1LL * (sum[j-1] - sum[j - i]) * (h[i])) % mod ) % mod;
			}
        }
        h[i] = 0;
        sum[i] = 0;
    }
    cout << ans << '\n';
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
        int t;
        cin >> t;
        while(t--)solve();
 
    return 0;
}

I2luY2x1ZGUgImJpdHMvc3RkYysrLmgiCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgbG9uZyBsb25nIGludCBsbDsKdHlwZWRlZiBwYWlyIDwgaW50ICwgaW50ID4gcDsKI2RlZmluZSByZXAoaSxhLG4pICBmb3IoaW50IGkgPSBhOyBpIDwgbjsgaSsrKQpjb25zdCBpbnQgbW9kID0gMTAwMDAwMzsKY29uc3QgaW50IE4gPSAyZTYrNTsKaW50IGhbTl0gPSB7MH0sIHN1bVtOXSA9IHswfTsKIAp2b2lkIHNvbHZlKCl7CiAgICBpbnQgbiwgaSwgbnVtO2ludCBlbGUgPSAwOwogICAgaW50IGFucygwKTsKICAgIGNpbiA+PiBuOwogCiAgICByZXAoaSwwLG4pY2luID4+IG51bSwgaFtudW1dKyssIHN1bVtudW1dKys7CiAgICByZXAoaSwxLE4pc3VtW2ldICs9IHN1bVtpLTFdOwogICAgZm9yKGludCBpID0gMTsgaSA8IE47IGkrKyl7CiAgICAgICAgaWYoaFtpXSl7CiAgICAgICAgCWVsZSA9IDA7CiAgICAgICAgCWZvcihpbnQgaiA9IGk7IGogPCBOOyBqICs9IGkpewoJICAgICAgICAgICAgYW5zID0gKGFucyAlIG1vZCArICgoaiAvIGkpICogMUxMICogaFtpXSAqIGhbal0pICUgbW9kKSAlIG1vZDsKCSAgICAgICAgICAgIGlmKGkgPT0gaiB8fCBpID09IDEpY29udGludWU7CgkgICAgICAgICAgIGFucyA9KGFucyAlIG1vZCArICggKChqLTEpIC8gaSkgKiAxTEwgKiAoc3VtW2otMV0gLSBzdW1baiAtIGldKSAqIChoW2ldKSkgJSBtb2QgKSAlIG1vZDsKCQkJfQogICAgICAgIH0KICAgICAgICBoW2ldID0gMDsKICAgICAgICBzdW1baV0gPSAwOwogICAgfQogICAgY291dCA8PCBhbnMgPDwgJ1xuJzsKfQpzaWduZWQgbWFpbigpewogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKTtjaW4udGllKE5VTEwpO2NvdXQudGllKE5VTEwpOwogICAgICAgIGludCB0OwogICAgICAgIGNpbiA+PiB0OwogICAgICAgIHdoaWxlKHQtLSlzb2x2ZSgpOwogCiAgICByZXR1cm4gMDsKfQ==

MQo1CjEgNSA0IDIgMw==

1
5
1 5 4 2 3