#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#pragma GCC optimize("O3,unroll-loops")
#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...)
#endif
#define endl '\n'
#define int int64_t
const long long mod = 1000000007, MaxN = 200005, INF = 1e10;
const int MAX = 1e5 + 5;
template <typename T>
struct BIT
{
	int sz;
	vector<T> tree;
	BIT() {};
	BIT(int N)
	{
		sz = N + 1;
		tree.resize(sz, -INF);
	}
	int lsb(int x)
	{
		return (x & -x);
	}
	void update(int idx, T x)
	{
		for (; idx < sz; idx += lsb(idx))
			tree[idx] = max(x, tree[idx]);
	}
	T get(int idx)
	{
		T Max = -INF;
		for (; idx; idx -= lsb(idx)){
			Max = max(Max, tree[idx]);
		}
		return Max;
	}
	
};
vector<BIT<int>>all(MAX);
vector<vector<int>>fact(MAX);
void solve()
{
	int N;
	cin >> N;
	vector<int> a(N + 1);
	for (int i = 1; i <= N; i++)
	{
		cin >> a[i];		
	}
	vector<int>dp(N + 1);
	for (int i = 1; i <= MAX; i++)
	{
		//bit[x][i] = max dp value where a[j] is divisble by x and a[j] <= i*x
		all[i] = BIT<int>(MAX / i + 3);
	}
	for (int i = 1; i <= N; i++)
	{
		for (auto &x : fact[a[i]])
		{
			//index of a[i] in the compressed form
			int idx = a[i] / x + 1;
			int y = all[x].get(idx);
			dp[i] = max(dp[i], y + x);
		}
		for(auto x : fact[a[i]]){
			int idx = a[i] / x + 1;
			//update the dp values with the new dp[i]
			all[x].update(idx, dp[i]);
		}
	}
	cout << *max_element(dp.begin(), dp.end()) << endl;
}
signed main()
{
	// freopen("mootube.in","r",stdin);
	// freopen("mootube.out","w",stdout);
	#ifdef LOCAL
	FileRedirect("test");
	#endif
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	cout.tie(nullptr);
	//precompute factors
	for(int i = 1;i < MAX;i++){
		for(int j = i;j < MAX;j += i){
			fact[j].push_back(i);
		}
	}	
	int Tc = 1;
	cin >> Tc;
	for (int T = 1; T <= Tc; T++)
		solve();
}