E 求调 & 求证D 复杂度

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

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using i128 = __int128;

using PII = pair<int, int>;
using PLL = pair<ll, ll>;

constexpr ll inf = (1ll << 62);
constexpr int N = 2e5 + 10;

template <typename T> void chkmax(T& a, T b) { a = max(a, b); }
template <typename T> void chkmin(T& a, T b) { a = min(a, b); }

void solve() {
	int n;
	cin >> n;
	map<PII, bool> tot;
	vector<vector<int>> adj(n);
	vector<int> cnt(n), st;
	vector<bool> flag(n);
	for (int i = 1; ; i++) {
		cout << "? " << i << endl;
		int x;
		cin >> x;
		if (!x) break;
		vector<int> d(x);
		for (int j = 0; j < x; j++) {
			cin >> d[j];
			d[j]--;
			if (!flag[d[j]]) cnt[d[j]]++;
			if (j && !tot[{d[j - 1], d[j]}]) {
				tot[{d[j - 1], d[j]}] = true;
				adj[d[j - 1]].emplace_back(d[j]);
			}
		}
		int pos = st.size();
		for (int j = 0; j < min(x, int(st.size())); j++) {
			if (st[j] != d[j]) {
				pos = j;
				break;
			}
		}
		while (st.size() > pos) {
			flag[st.back()] = true;
			st.pop_back();
		}
		for (int j = pos; j < x; j++) st.emplace_back(d[j]);
		if (flag[d.back()]) {
			for (int j = 0; j < x - 1; j++) {
				cnt[d[j]] += cnt[d.back()] - 1;
			}	
			i += cnt[d.back()] - 1;
			st.pop_back();
		}
	}
	int sum = 0;
	for (int i = 0; i < n; i++) sum += adj[i].size();
	cout << "! " << sum << endl;
	for (int i = 0; i < n; i++) {
		for (auto j : adj[i]) {
			cout << i + 1 << " " << j + 1 << endl;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t = 1;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

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

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using i128 = __int128;

using PII = pair<int, int>;
using PLL = pair<ll, ll>;

constexpr ll inf = (1ll << 62);
constexpr int N = 2e5 + 10;

template <typename T> void chkmax(T& a, T b) { a = max(a, b); }
template <typename T> void chkmin(T& a, T b) { a = min(a, b); }

void solve() {
	int n;
	ll ans = 0;
	cin >> n;
	vector<int> a(n), tot(n);
	vector<vector<int>> pos(n + 1);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		if (a[i] <= n) pos[a[i]].emplace_back(i);
	}
	for (int i = 1; i <= n; i++) {
		if (!pos[i].size()) continue;
		for (auto j : pos[i]) tot[j]++;
		for (int j = i; j <= n; j += i) {
			ll x = j, cnt = 0;
			for (auto k : pos[j / i]) {
				if (k - x >= 0) {
					cnt += tot[k - x];
				}
				if (k + x < n) {
					cnt += tot[k + x];
				}
			}
			ans += cnt;
		}
		for (auto j : pos[i]) tot[j]--;
	}
	cout << ans / 2 << "\n";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t = 1;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}