#include <bits/stdc++.h>
using namespace std;
 
const int sz = 1e5 + 10;
int ara[sz];
 
int main()
{
    int t;
    scanf("%d", &t);
 
    while(t--) {
        int n;
        scanf("%d", &n);
 
        int sum = 0;
 
        for(int i = 1; i <= n; i++) {
            scanf("%d", &ara[i]);
            sum += ara[i];
        }
 
        int ans = -1e9;
 
        for(int i = 1; i < n; i++) {
            if(ara[i] == ara[i+1]) {
                if(ara[i] == 1) ans = max(ans, sum-4);
                else ans = max(ans, sum+4);
            }
            else
                ans = max(ans, sum);
        }
 
        printf("%d\n", ans);
    }
 
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
const int sz = 1e5+10;
int p[sz], a[sz], pos[sz];
 
int main()
{
    int t;
    scanf("%d", &t);
 
    while(t--) {
        int n, m, d;
        scanf("%d %d %d", &n, &m, &d);
 
        for(int i = 1; i <= n; i++) {
            scanf("%d", &p[i]);
            pos[ p[i] ] = i;
        }
 
        for(int i = 1; i <= m; i++) {
            scanf("%d", &a[i]);
        }
 
        int ans = 1e9;
 
        for(int i = 1; i < m; i++) {
            if(pos[a[i+1]] <= pos[a[i]] || pos[a[i+1]]-pos[a[i]] > d) {
                ans = 0;
                break;
            }
 
            ans = min(ans, pos[a[i+1]] - pos[a[i]]);
 
            int dist = pos[a[i+1]]-pos[a[i]];
 
            int swapNeed = d-dist+1;
            int swapPossible = (pos[a[i]]-1) + (n - pos[a[i+1]]);
            if(swapPossible >= swapNeed) ans = min(ans, swapNeed);
        }
 
        printf("%d\n", ans);
    }
 
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pb push_back
#define EL '\n'
#define fastio std::ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
string a, b;
string char_list;
bool mark[26];
ll ans, k;
 
ll count_matching_pair()
{
    ll tot_pair = 0, match_count = 0;
 
    for(ll i = 0; i < a.size(); i++) {
        if(a[i] == b[i] || mark[ a[i]-'a' ])
            match_count++;
        else {
            tot_pair += match_count*(match_count+1)/2;
            match_count = 0;
        }
    }
    tot_pair += match_count*(match_count+1)/2;
 
    return tot_pair;
}
 
void solve(ll pos, ll cnt)
{
    if(cnt > k) return;
 
    if(pos == char_list.size()) {
        if(cnt == k) ans = max(ans, count_matching_pair());
        return;
    }
 
    solve(pos+1, cnt);
 
    mark[ char_list[pos]-'a' ] = 1;
    solve(pos+1, cnt+1);
    mark[ char_list[pos]-'a' ] = 0;
}
 
int main()
{
    fastio;
    ll t;
    cin >> t;
 
    while(t--) {
        ll n; cin >> n >> k;
        cin >> a >> b;
 
        unordered_set <char> unq;
        for(auto &ch : a) unq.insert(ch);
 
        char_list.clear();
        for(auto &x : unq) char_list.pb(x);
 
        k = min(k, (ll)unq.size());
        memset(mark, 0, sizeof mark);
        ans = 0;
        solve(0, 0);
 
        cout << ans << EL;
    }
 
    return 0;
}

1778D - Flexible String Revisit

Let $$$k$$$ be the number of indices where the characters between two strings are different and $$$f(x)$$$ be the expected number of moves to make two strings equal given that the strings have $$$x$$$ differences. We have to find the value of $$$f(k)$$$.

For all $$$x$$$ where $$$1 \leq x \leq n-1$$$,

Now, $$$f(0) = 0$$$ and $$$f(1) = 1 + \frac{n-1}{n}f(2)$$$.

We can represent any $$$f(i)$$$ in the form $$$f(i) = a_i + b_i \cdot f(i+1)$$$.

Let, $$$a_{1} = 1$$$ and $$$b_{1} = \frac{n-1}{n}$$$. So, we can write $$$f(1) = a_{1} + b_{1}\cdot f(2)$$$.

When $$$1 \lt i \lt n$$$, $$$f(i) = 1 + \frac{i}{n} \cdot f(i-1) + \frac{n-i}{n} \cdot f(i+1)$$$. We can substitute the value of $$$f(i-1)$$$ with $$$a_{i-1} + b_{i-1}\cdot f(i)$$$ and calculate the value of $$$f(i)$$$. Thus we can get the value of $$$a_i$$$ and $$$b_i$$$ using the value of $$$a_{i-1}$$$ and $$$b_{i-1}$$$ by considering $$$a_1$$$ and $$$b_1$$$ as the base case.

We get, $$$a_{i} = \frac{n+i\cdot a_{i-1}}{n-i\cdot b_{i-1}}$$$ and $$$b_{i} = \frac{n-i}{n-i \cdot b_{i-1}}$$$ for $$$2 \leq i \leq n$$$.

Similarly, $$$f(n) = 1+f(n-1)$$$.

We can represent any $$$f(i)$$$ in the form $$$f(i) = c_i + d_i \cdot f(i-1)$$$.

Let, $$$c_{n} = 1$$$ and $$$d_{n} = 1$$$. So, we can write $$$f(n) = c_{n} + d_{n}\cdot f(n-1)$$$.

When $$$1 \lt i \lt n$$$, $$$f(i) = 1 + \frac{i}{n} \cdot f(i-1) + \frac{n-i}{n} \cdot f(i+1)$$$. We can substitute the value of $$$f(i+1)$$$ with $$$c_{i+1} + d_{i+1}\cdot f(i)$$$ and calculate the value of $$$f(i)$$$. Thus we can get the value of $$$c_i$$$ and $$$d_i$$$ using the value of $$$c_{i+1}$$$ and $$$d_{i+1}$$$ by considering $$$c_n$$$ and $$$d_n$$$ as the base case.

We get, $$$c_{i} = \frac{n+(n-i)\cdot c_{i+1}}{n-(n-i)\cdot d_{i+1}}$$$ and $$$d_{i} = \frac{i}{n-(n-i) \cdot d_{i+1}}$$$.

Now, $$$f(i) = c_i + d_i \cdot f(i-1)$$$ and $$$f(i-1) = a_{i-1} + b_{i-1} \cdot f(i)$$$. By solving these two equations, we find that $$$f(i) = \frac{c_i+d_i \cdot a_{i-1}}{1-d_i \cdot b_{i-1}}$$$.

Time Complexity: $$$\mathcal{O}(n\cdot \log m)$$$.

After some calculations, it can be shown that $$$f(1) = 2^n - 1$$$. Now we know $$$f(0) = 0$$$ and $$$f(1) = 2^n - 1$$$.

From the relation between $$$f(i)$$$, $$$f(i-1)$$$ and $$$f(i-2)$$$, we can write $$$f(i) = \frac{n\cdot f(i-1) - i \cdot f(i-2) - n}{n-i+1}$$$.

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

#define mod 998244353 
#define N 1000005
 
template<int MOD>
struct ModInt {
  unsigned x;
  ModInt() : x(0) { }
  ModInt(signed sig) : x(sig) {  }
  ModInt(signed long long sig) : x(sig%MOD) { }
  int get() const { return (int)x; }
  ModInt pow(ll p) { ModInt res = 1, a = *this; while (p) { if (p & 1) res *= a; a *= a; p >>= 1; } return res; }
 
  ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
  ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
  ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
  ModInt &operator/=(ModInt that) { return (*this) *= that.pow(MOD - 2); }
 
  ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
  ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
  ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
  ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
  bool operator<(ModInt that) const { return x < that.x; }
  friend ostream& operator<<(ostream &os, ModInt a) { os << a.x; return os; }
};
typedef ModInt<998244353> mint;
 
mint a[N], b[N], c[N], d[N];
 
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
 
        string s1, s2;
        cin >> s1 >> s2;
 
        int diff = 0;
        for(int i = 0; i < n; i++){
            diff += s1[i]!=s2[i];
        }
 
        c[n] = 1, d[n] = 1, a[1] = 1, b[1] = ((mint) n-1)/n;
 
        for(int i = 2; i <= n; i++){
            a[i] = ((mint) n + a[i-1]*i)/((mint) n - b[i-1]*i);
            b[i] = ((mint) n-i)/((mint) n - b[i-1]*i);
        }
 
        for(int i = n-1; i >= 1; i--){
            c[i] = ((mint) n + c[i+1]*(n-i))/((mint) n - d[i+1]*(n-i));
            d[i] = (mint) i / ((mint) n - d[i+1]*(n-i));
        }
 
        mint ans = (c[diff]+d[diff]*a[diff-1])/((mint) 1 - d[diff]*b[diff-1]);
 
        cout << ans << endl;
    }
 
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
 
template<int MOD>
struct ModInt {
  unsigned x;
  ModInt() : x(0) { }
  ModInt(signed sig) : x(sig) {  }
  ModInt(signed long long sig) : x(sig%MOD) { }
  int get() const { return (int)x; }
  ModInt pow(ll p) { ModInt res = 1, a = *this; while (p) { if (p & 1) res *= a; a *= a; p >>= 1; } return res; }
 
  ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
  ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
  ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
  ModInt &operator/=(ModInt that) { return (*this) *= that.pow(MOD - 2); }
 
  ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
  ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
  ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
  ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
  bool operator<(ModInt that) const { return x < that.x; }
  friend ostream& operator<<(ostream &os, ModInt a) { os << a.x; return os; }
};
typedef ModInt<998244353> mint;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    mint two = 2;
 
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
 
        string a, b;
        cin >> a >> b;
 
        int cnt = 0;
        for(int i = 0; i < n; i++){
            if(a[i]!=b[i]) cnt++;
        }
 
        vector<mint> dp(n+2);
        dp[0] = two.pow(n);
        dp[1] = dp[0]-1;
        dp[0] = 0;
 
        for(long long i = 2; i < n; i++){
            mint x = i-1;
            x /= n;
            dp[i] = (dp[i-1]-x*dp[i-2]-1)*n/(n-i+1);
        }
 
        dp[n] = dp[n-1]+1;
 
        cout << dp[cnt] << '\n';
    }
 
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pb push_back
#define nn '\n'
#define fastio std::ios_base::sync_with_stdio(false); cin.tie(NULL);
 
const int sz = 2e5 + 10, d = 30;
vector <int> g[sz], Tree[sz];
int a[sz], discover_time[sz], finish_time[sz], nodeOf[sz], tim;
 
struct BASIS {
    int basis[d];
    int sz;
 
    void init() {
        for(int i = 0; i < d; i++) basis[i] = 0;
        sz = 0;
    }
 
    void insertVector(int mask) {
        for (int i = d-1; i >= 0; i--) {
            if (((mask>>i)&1) == 0) continue;
 
            if (!basis[i]) {
                basis[i] = mask;
                ++sz;
                return;
            }
            mask ^= basis[i];
        }
    }
 
    void mergeBasis(const BASIS &from) {
        for(int i = d-1; i >= 0; i--) {
            if(!from.basis[i])
                continue;
 
            insertVector(from.basis[i]);
        }
    }
 
    int findMax()  {
        int ret = 0;
        for(int i = d-1; i >= 0; i--) {
            if(!basis[i] || (ret>>i & 1))
                continue;
 
            ret ^= basis[i];
        }
        return ret;
    }
} in[sz], out, pre[sz], suf[sz];
 
void in_dfs(int u, int p)
{
    in[u].insertVector(a[u]);
    discover_time[u] = ++tim;
    nodeOf[tim] = u;
 
    for(auto &v : g[u]) {
        if(v == p)
            continue;
 
        Tree[u].pb(v);
        in_dfs(v, u);
 
        in[u].mergeBasis(in[v]);
    }
    finish_time[u] = tim;
}
 
inline bool in_subtree(int sub_root, int v)
{
    return discover_time[sub_root] <= discover_time[v]
            && finish_time[sub_root] >= finish_time[v];
}
 
int findChildOnPath(int sub_root, int v)
{
    int lo = 0, hi = (int)Tree[sub_root].size()-1;
 
    while(lo <= hi) {
        int mid = lo+hi>>1, node = Tree[sub_root][mid];
 
        if(finish_time[node] < discover_time[v])
            lo = mid + 1;
        else if(discover_time[node] > discover_time[v])
            hi= mid - 1;
        else
            return node;
    }
}
 
void init(int n) {
 
    for(int i = 0; i <= n+5; i++) {
        g[i].clear(), Tree[i].clear();
        in[i].init();
        pre[i].init(), suf[i].init();
    }
    tim = 0;
}
 
int main()
{
    fastio;
 
    int t;
    cin >> t;
 
    while(t--) {
        int n; cin >> n;
 
        init(n);
 
        for(int i = 1; i <= n; i++) cin >> a[i];
 
        for(int i = 1; i < n; i++) {
            int u, v;
            cin >> u >> v;
            g[u].pb(v); g[v].pb(u);
        }
 
        in_dfs(1, -1);
 
        for(int i = 1; i <= n; i++) {
            pre[i].insertVector(a[ nodeOf[i] ]);
            pre[i].mergeBasis(pre[i-1]);
        }
 
        for(int i = n; i >= 1; i--) {
            suf[i].insertVector(a[ nodeOf[i] ]);
            suf[i].mergeBasis(suf[i+1]);
        }
 
        int q; cin >> q;
 
        while(q--) {
            int root, v;
            cin >> root >> v;
 
            if(root == v) {
                cout << in[1].findMax() << nn;
            }
            else if(in_subtree(v, root)) {
                int child = findChildOnPath(v, root);
 
                out.init();
                out.mergeBasis(pre[discover_time[child]-1]);
                out.mergeBasis(suf[finish_time[child]+1]);
                cout << out.findMax() << nn;
            }
            else
                cout << in[v].findMax() << nn;
        }
    }
 
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
const int N = 100005;
const int mod = 998244353;
 
int val[N];
vector<int> g[N];
vector<int> divisor[N];
int subtree_gcd[N], par[N];
 
int dp[N][1003];
int gcdd[1003][1003];
 
inline long long ___gcd(long long a, long long b){
    if(gcdd[a][b]) return gcdd[a][b];
 
    return gcdd[a][b] = __gcd(a, b);
}
 
inline long long lcm(long long a, long long b){
    return (a/___gcd(a, b))*b;
}
 
void dfs(int u, int p){
    par[u] = p;
    subtree_gcd[u] = val[u];
    for(int v: g[u]){
        if(v==p) continue;
        dfs(v, u);
        subtree_gcd[u] = ___gcd(subtree_gcd[u], subtree_gcd[v]);
    }
}
 
 
int solve(int u, int d, int p){
    if(subtree_gcd[u]%d==0) return 0;
    if((val[u]*val[u])%d) return (1<<30);
 
 
    if(dp[u][d]!=-1) return dp[u][d];
    
    long long req = d/___gcd(d, subtree_gcd[u]);
 
    long long res = (1<<30);
    for(int div: divisor[val[u]]){
        if((val[u]*div)%d==0 && d%div==0){
            long long r = 1;
            for(int v: g[u]){
                if(v==p) continue;
                r += solve(v, lcm(d/div, div), u);
            }
            res = min(res, r);
        }
    }
 
    return dp[u][d] = min(res, (1LL<<30));
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    for(int i = 2; i < 1001; i++){
        for(int j = i; j < 1001; j+=i){
            divisor[j].push_back(i);
        }
    }
 
    int t;
    cin >> t;
 
    while(t--){
        int n, k;
        cin >> n >> k;
 
        for(int i = 0; i <= n; i++){
            g[i].clear();
        }
 
        for(int i = 1; i <= n; i++){
            cin >> val[i];
        }
        
        for(int i = 0; i <= n; i++){
            for(int d: divisor[val[1]]){
                dp[i][d] = -1;
            }
        }
 
        for(int i = 0; i < n-1; i++){
            int u, v;
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
 
        dfs(1, 0);
 
        int ans = val[1];
 
        for(int d: divisor[val[1]]){
            int req = 0;
            int f = 1;
            for(int v: g[1]){
                int x = solve(v, d, par[v]);
                if(x>n) f = 0;
                req += x;
            }
 
            if(!f) continue;
 
            req++;
            if(req<=k){
                ans = max(ans, val[1]*d);
            }
        }
 
        cout << ans << "\n";
    }
    
    return 0;
}