def go(bubbles, col, row):
    n = len(bubbles)
    row = min(row, n - 1)
    t = row
    for i in range(row, -1, -1):
        if bubbles[i][col] != 0:
            bubbles[t][col] = bubbles[i][col]
            t -= 1
    for i in range(t, -1, -1):
        bubbles[i][col] = 0
def solution(bubbles):
    m, n = len(bubbles), len(bubbles[0])
    dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1]
    to_explode = set()
    for x in range(m):
        for y in range(n):
            if bubbles[x][y] == 0:
                continue
            c = 0
            color = bubbles[x][y]
            for d in range(4):
                xx, yy = x + dx[d], y + dy[d]
                if 0 <= xx < m and 0 <= yy < n and bubbles[xx][yy] == color:
                    c += 1
            if c >= 2:
                to_explode.add((x, y))
                for d in range(4):
                    xx, yy = x + dx[d], y + dy[d]
                    if 0 <= xx < m and 0 <= yy < n and bubbles[xx][yy] == color:
                        to_explode.add((xx, yy))
    for x, y in to_explode:
        bubbles[x][y] = 0
    for y in range(n):
        go(bubbles, y, m - 1)
    return bubbles

long maxScoreAfterKOperations(vector<int>& arr, int k) {
    priority_queue<int> maxHeap(arr.begin(), arr.end());
    long q = 0;
    for (int i = 0; i < k; ++i) {
        long maxElement = maxHeap.top();
        maxHeap.pop();
        q += maxElement;
        long newElement = ceil(maxElement / 3.0);
        maxHeap.push(newElement);
    }
    return q;
}

def longestEvenSumSubsequence(arr):
    n = len(arr)
    arr.sort()
    s = 0
    for i in range(1, n):
        s += arr[i] - arr[i - 1]
    if s % 2 == 0:
        return n 
    else:
        for i in range(n):
            f = s - arr[i] + arr[i - 1] if i > 0 else s - arr[1] + arr[0]
            if f % 2 == 0:
                return n - 1 
    return 0

#include <bits/stdc++.h>
#define endl '\n'
#define ll long long int
#define pb push_back
#define pf push_front
#define F first
#define S second
const ll MOD = 1e9 + 7;

using namespace std;

ll solve(int n, int k, int m) {
    vector<vector<ll>> dp(k + 1, vector<ll>(m, 0));
    dp[0][0] = 1;

    for (ll num = 0; num < n; num++) {
        vector<vector<ll>> new_dp = dp;
        for (ll size = 1; size <= k; size++) {
            for (ll rem = 0; rem < m; rem++) {
                ll new_rem = (rem + num) % m;
                new_dp[size][new_rem] = (new_dp[size][new_rem] + dp[size - 1][rem]) % MOD;
            }
        }
        dp = new_dp;
    }

    return dp[k][0];
}

#include <iostream>
#include <vector>
using namespace std;

class UnionFind {
public:
    vector<int> parent, rank, size;

    UnionFind(int n) : parent(n), rank(n, 1), size(n, 1) {
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
                size[rootX] += size[rootY];
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
                size[rootY] += size[rootX];
            } else {
                parent[rootY] = rootX;
                size[rootX] += size[rootY];
                rank[rootX]++;
            }
        }
    }

    int getSize(int x) {
        int rootX = find(x);
        return size[rootX];
    }
};

long long countPairs(int n, int k, vector<int>& u, vector<int>& v) {
    UnionFind uf(n);
    for (int i = 0; i < k; ++i) {
        uf.unionSets(u[i], v[i]);
    }
    long long totalPairs = (long long)n * (n - 1) / 2;
    vector<bool> visited(n, false);
    for (int i = 0; i < n; ++i) {
        int root = uf.find(i);
        if (!visited[root]) {
            visited[root] = true;
            int clusterSize = uf.getSize(i);
            if (clusterSize > 1) {
                totalPairs -= (long long)clusterSize * (clusterSize - 1) / 2;
            }
        }
    }

    return totalPairs;
}