#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int n;
vector<long long> a;
vector<vector<int>> adj;
vector<int> subtree_size;
long long total_good_triplets;

// 检查是否为完美平方数
bool is_perfect_square(long long x) {
    long long r = round(sqrt(x));
    return r * r == x;
}

void dfs(int u, int p) {
    subtree_size[u] = 1;
    vector<long long> comp_sizes;
    
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        subtree_size[u] += subtree_size[v];
        comp_sizes.push_back(subtree_size[v]); // 子树构成一个连通块
    }
    
    if (u != 1) {
        comp_sizes.push_back(n - subtree_size[u]); // 父亲方向的剩余部分构成一个连通块
    }
    
    // 如果当前节点是完美平方数，统计以它为核心的中位数三元组
    if (is_perfect_square(a[u])) {
        long long S1 = 0, S2 = 0, S3 = 0;
        for (long long s : comp_sizes) {
            S1 += s;
            S2 += s * s;
            S3 += s * s * s;
        }
        
        // E2 = sum_{a < b} s_a * s_b
        long long E2 = (S1 * S1 - S2) / 2;
        // E3 = sum_{a < b < c} s_a * s_b * s_c
        long long E3 = (S1 * S1 * S1 - 3 * S1 * S2 + 2 * S3) / 6;
        
        total_good_triplets += (E2 + E3);
    }
}

void solve() {
    cin >> n;
    a.resize(n + 1);
    adj.assign(n + 1, vector<int>());
    subtree_size.resize(n + 1);
    total_good_triplets = 0;
    
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    dfs(1, 0);
    cout << total_good_triplets << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <string>

using namespace std;

void print128(__int128 num) {
    if (num == 0) {
        cout << 0 << "\n";
        return;
    }
    string buf;
    while (num > 0) {
        buf += (char)('0' + (num % 10));
        num /= 10;
    }
    reverse(buf.begin(), buf.end());
    cout << buf << "\n";
}

void solve() {
    int arr_len;
    if (!(cin >> arr_len)) return;
    vector<long long> arr(arr_len + 1);
    for (int pos = 1; pos <= arr_len; ++pos) {
        cin >> arr[pos];
    }
    
    __int128 sum_total = 0;
    vector<pair<long long, int>> seg_gcd_list;
    
    for (int left_pt = arr_len; left_pt >= 1; --left_pt) {
        long long base_val = arr[left_pt];
        vector<pair<long long, int>> new_seg_gcd;
        long long curr_gcd = base_val;
        int last_seg_r = left_pt;
        
        for (auto& seg_item : seg_gcd_list) {
            long long new_g = gcd(curr_gcd, seg_item.first);
            if (new_g == curr_gcd) {
                last_seg_r = seg_item.second;
            } else {
                new_seg_gcd.push_back({curr_gcd, last_seg_r});
                curr_gcd = new_g;
                last_seg_r = seg_item.second;
            }
        }
        new_seg_gcd.push_back({curr_gcd, last_seg_r});
        seg_gcd_list.swap(new_seg_gcd);
        
        vector<pair<int, long long>> split_point_list;
        int seg_start = left_pt;
        for (int idx = 0; idx < (int)seg_gcd_list.size(); ++idx) {
            if (idx > 0) {
                split_point_list.push_back({seg_start, seg_gcd_list[idx - 1].first});
            }
            seg_start = seg_gcd_list[idx].second + 1;
        }
        
        vector<pair<long long, long long>> interval_set;
        int curr_r_begin = left_pt;
        
        for (int sp_idx = 0; sp_idx <= (int)split_point_list.size(); ++sp_idx) {
            int next_r_begin = (sp_idx < (int)split_point_list.size()) ? split_point_list[sp_idx].first : arr_len + 1;
            
            long long block_length = next_r_begin - curr_r_begin;
            if (block_length > 0) {
                long long min_diff = 0;
                if (!interval_set.empty()) {
                    vector<pair<long long, long long>> sorted_intervals = interval_set;
                    sort(sorted_intervals.begin(), sorted_intervals.end());
                    
                    long long res_min = 2e18;
                    long long max_right = base_val;
                    for (int i = 0; i < (int)sorted_intervals.size(); ++i) {
                        res_min = min(res_min, max_right - sorted_intervals[i].first);
                        max_right = max(max_right, sorted_intervals[i].second);
                    }
                    res_min = min(res_min, max_right - base_val);
                    min_diff = res_min;
                }
                sum_total += (__int128)min_diff * block_length;
            }
            
            if (sp_idx < (int)split_point_list.size()) {
                int split_pos = split_point_list[sp_idx].first;
                long long gcd_split = split_point_list[sp_idx].second;
                long long num_val = arr[split_pos];
                long long rem_diff = (base_val % gcd_split - num_val % gcd_split + gcd_split) % gcd_split;
                if (rem_diff > 0) {
                    long long l_bound = base_val - rem_diff;
                    long long r_bound = base_val - rem_diff + gcd_split;
                    interval_set.push_back({l_bound, r_bound});
                }
            }
            curr_r_begin = next_r_begin;
        }
    }
    print128(sum_total);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int test_cnt;
    if (cin >> test_cnt) {
        while (test_cnt--) {
            solve();
        }
    }
    return 0;
}

// using namespace std;

// bool isSquare(long long x){
//     if(x < 0) return false;
//     long long r = round(sqrt(x));
//     return r * r == x;
// }

// void solve(){
//     int n;
//     cin >> n;

//     vector<long long> a(n + 1);
//     for(int i = 1; i <= n; i++){
//         cin >> a[i];
//     }

//     vector<vector<int>> adj(n + 1);
//     for(int i = 0; i < n - 1; i++){
//         int u, v;
//         cin >> u >> v;
//         adj[u].push_back(v);
//         adj[v].push_back(u);
//     }

//     vec
// }

// int main()
// {
//     ios_base::sync_with_stdio(false);
//     cin.tie(NULL);
//     int t;
//     cin >> t;
//     while (t--)
//     {

//     }
// }

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

// Fast check for perfect square
bool is_square(long long x) {
    if (x < 0) return false;
    long long r = round(sqrt(x));
    return r * r == x;
}

void solve() {
    int n;
    cin >> n;
    
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> sz(n + 1, 0);
    long long total_good_triplets = 0;

    // DFS to calculate subtree sizes and count valid triplets
    auto dfs = [&](auto& self, int u, int p) -> void {
        sz[u] = 1;
        vector<int> component_sizes;
        
        for (int v : adj[u]) {
            if (v != p) {
                self(self, v, u);
                sz[u] += sz[v];
                component_sizes.push_back(sz[v]);
            }
        }
        
        // Add the component representing the rest of the tree (if u is not the root)
        if (n - sz[u] > 0) {
            component_sizes.push_back(n - sz[u]);
        }

        // If the current node is a valid median (its value is a perfect square)
        if (is_square(a[u])) {
            long long A = 0; // Ways to pick 3 nodes from different components
            long long B = 0; // Ways to pick 2 nodes from different components (3rd node is u)
            long long sum = 0;
            long long sum_pairs = 0;
            
            // Calculate combinations dynamically to maintain O(degree) complexity
            for (long long s : component_sizes) {
                A += sum_pairs * s;
                sum_pairs += sum * s;
                B += sum * s;
                sum += s;
            }
            total_good_triplets += (A + B);
        }
    };

    dfs(dfs, 1, 0);
    cout << total_good_triplets << "\n";
}

int main() {
    // Optimize standard I/O operations for competitive programming
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXA = 1000005;
int min_prime[MAXA];

void sieve() {
    for (int i = 2; i * i < MAXA; ++i) {
        if (min_prime[i] == 0) {
            for (int j = i * i; j < MAXA; j += i) {
                if (min_prime[j] == 0) min_prime[j] = i;
            }
        }
    }
    for (int i = 2; i < MAXA; ++i) {
        if (min_prime[i] == 0) min_prime[i] = i;
    }
}

bool is_perfect_square(int n) {
    if (n == 1) return true;
    int temp = n;
    while (temp > 1) {
        int p = min_prime[temp];
        int count = 0;
        while (temp % p == 0) {
            count++;
            temp /= p;
        }
        if (count % 2 == 1) return false;
    }
    return true;
}

void dfs_sz(int u, int p, const vector<vector<int>>& adj, vector<int>& sz) {
    sz[u] = 1;
    for (int v : adj[u]) {
        if (v != p) {
            dfs_sz(v, u, adj, sz);
            sz[u] += sz[v];
        }
    }
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<bool> is_sq(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        is_sq[i] = is_perfect_square(a[i]);
    }

    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> sz(n + 1);
    dfs_sz(1, 0, adj, sz);

    ll squarewf = 0;

    for (int i = 1; i <= n; ++i) {
        if (is_sq[i]) {
            vector<ll> comps;
            for (int v : adj[i]) {
                if (sz[v] < sz[i]) {
                    comps.push_back(sz[v]);
                } else {
                    comps.push_back(n - sz[i]);
                }
            }

            ll s1 = 0, s2 = 0, s3 = 0;
            for (ll c : comps) {
                s1 += c;
                s2 += c * c;
                s3 += c * c * c;
            }

            ll pairs = (s1 * s1 - s2) / 2;
            ll trips = (s1 * s1 * s1 - 3 * s1 * s2 + 2 * s3) / 6;

            squarewf += pairs + trips;
        }
    }
    cout << squarewf << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    sieve();
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}