class Investment:
    @staticmethod
    def times_of_investment(input1, input2):
        A = sum(input2)
        Res = 0
        while A % 2 == 0 and A != 0:
            A //= 2
            Res += 1
        return Res

int mrt2(const string& st) {
    int n = st.length();
    vector<vector<int>> lst(n, vector<int>(n, 0));
    for (int i = 0; i < n; ++i)
        lst[i][i] = 1;

    for (int k = 2; k <= n; ++k) {
        for (int i = 0; i <= n - k; ++i) {
            int j = i + k - 1;
            if (st[i] == st[j]) {
                if (k == 2)
                    lst[i][j] = 2;
                else
                    lst[i][j] = lst[i + 1][j - 1] + 2;
            } else {
                lst[i][j] = max(lst[i + 1][j], lst[i][j - 1]);
            }
        }
    }
    return lst[0][n - 1];
}

int delete_op(const string& st) {
    int n = st.length();
    int lps = mrt2(st);
    return n - lps;
}

bool rearrange(const string& S) {
    unordered_map<char, int> freq;
    for (char c : S) {
        freq[c]++;
    }

    int odd_count = 0;
    for (auto& p : freq) {
        if (p.second % 2 == 1)
            odd_count++;
    }

    return odd_count <= 1;
}

vector<int> mrt(const string& S, const vector<pair<int, int>>& arr) {
    vector<int> res;
    for (auto& range : arr) {
        string temp = S.substr(range.first - 1, range.second - range.first + 1);
        int result = rearrange(temp) ? 0 : delete_op(temp);
        res.push_back(result);
    }
    return res;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int minimizeDiff(int a, vector<int>& b) {
    int c = b.size();
    int d = *max_element(b.begin(), b.end());
    int e = *min_element(b.begin(), b.end());
    if ((d - e) <= a) {
        return (d - e);
    }
    int f = (d + e) / 2;
    for (int g = 0; g < c; g++) {
        if (b[g] > f) {
            b[g] -= a;
        } else {
            b[g] += a;
        }
    }
    d = *max_element(b.begin(), b.end());
    e = *min_element(b.begin(), b.end());
    return (d - e);
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const ll mod = 1e9 + 7;

ll add(ll x, ll y)
{
    return (x + y) % mod;
}

ll mul(ll x, ll y)
{
    return (x * y) % mod;
}


ll dp[101][101][101];
ll solver(ll i, ll maxm, ll n, ll m, ll totalCost)
{
    if (i == n)
    {
        if (totalCost == 0)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }


    if (dp[i][maxm][totalCost] != -1)
    {
        return dp[i][maxm][totalCost];
    }

    ll temp = 0;

    for (int j = 1;j <= m;j++)
    {
        if (j > maxm)
        {
            temp = add(temp, solver(i + 1, j, n, m, totalCost - 1));
        }
        else
        {
            temp = add(temp, solver(i + 1, maxm, n, m, totalCost));
        }
    }


    return dp[i][maxm][totalCost] = temp;

}




void solve(vector<ll>n, vector<ll> m, vector<ll> totalCost)
{



    ll q = n.size();

    vector<ll>answer(q);



    for (int j = 0;j < q;j++)
    {

        memset(dp, -1, sizeof(dp));


        ll N= n[j];
        ll M= m[j];
        ll Tot= totalCost[j];

        ll ans = 0;
        for (int i = 1;i <= M;i++)
        {
            ans = add(ans, solver(1, i, N, M, Tot));
        }
        answer.push_back(ans);

    }

    for (int j = 0;j < q;j++)
    {
        cout << answer[j] << endl;
    }

    return;


}

def stringOperation(start, fin):
    n, m = len(start), len(fin)
    res = []
    for s in fin:
        found = False
        for t in start:
            if len(s) == len(t) and sum(a != b for a, b in zip(s, t)) == 1:
                found = True
                break
        res.append("YES" if found else "NO")
    return res

vector<int> solution(vector<int> numbers) {
    if (numbers.size() < 2) return numbers;
    
    vector<int> f = {numbers[0]}, s = {numbers[1]};
    
    for (int i = 2; i < numbers.size(); ++i) {
        int cf = 0, cs = 0;
        for (int x : f) cf += x > numbers[i];
        for (int x : s) cs += x > numbers[i];
        
        if (cf > cs || (cf == cs && f.size() <= s.size())) {
            f.push_back(numbers[i]);
        } else {
            s.push_back(numbers[i]);
        }
    }
    
    f.insert(f.end(), s.begin(), s.end());
    return f;
}

import math
def b(x):
    s = int(math.sqrt(x))
    return s * s == x
def solve(A):
    n = len(A)
    y = 0
    for i in range(n):
        for j in range(i + 1, n):
            while b(A[i] * A[j]):
                if A[i] > 1:
                    A[i] += 1
                    y += 1
                elif A[j] > 1:
                    A[j] += 1
                    y += 1
                else:
                    A[i] += 1
                    y += 1
    return y