引理：对于任意一个前缀，最优解里含有 $2$ 的幂次的数字不会超过 $\mathcal O(\log V)$ 个。

直接对每个前缀暴力维护这些位置，从前缀 $i$ 转移到前缀 $i+1$ 时，先将前缀 $i$ 有值的位置排序，然后转移给 $i+1$ 的肯定是一个前缀，暴力枚举它。比较若干 $\sum a2^b$ 的大小不是很难。

这样总复杂度是 $\mathcal O(n \log^2 V)$ 的，在 CF 上跑了 2187ms，只差 0.2 秒了，求卡常 qwq。

/**
 *    author: sunkuangzheng
 *    created: 27.10.2024 23:21:38
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 2e5+5,mod = 1e9 + 7;
using namespace std;
int T,n,a[N],pw[N];
int qp(ll a,int b){
    int r = 1; a %= mod;
    for(;b;b >>= 1,a = 1ll * a * a % mod) if(b & 1) r = 1ll * r * a % mod;
    return r; 
}struct num{
    ll a,b; // a * 2^b
    bool operator <(const num&x) const{
        int d = min(b,x.b),r = max(b,x.b);
        if(r - d >= 50) return b < x.b;
        else return (__int128)a * (1ll << b - d) < (__int128)x.a * (1ll << x.b - d);
    }int val(){
        return 1ll * a % mod * qp(2,b) % mod;
    }
}p[N];
ll pa[N * 30];
__int128 abs(__int128 x){return x >= 0 ? x : -x;}
int t[N],cnt;
bool cmp(vector<num> &a,vector<num> &b){
    cnt = 0;
    for(auto [x,y] : a) pa[y] = 0;
    for(auto [x,y] : b) pa[y] = 0;
    for(auto [x,y] : a) pa[y] += x,t[cnt ++] = y;
    for(auto [x,y] : b) pa[y] -= x,t[cnt ++] = y;
    sort(t,t+cnt,greater()),cnt = unique(t,t+cnt) - t;
    for(int i = 1;i < cnt;i ++){
        if(pa[t[i-1]] && t[i-1] - t[i] >= 50 || abs((__int128)pa[t[i-1]] * (1ll << t[i-1] - t[i])) >= 1e15) return pa[t[i-1]] > 0;
        pa[t[i]] += pa[t[i-1]] * (1ll << t[i-1] - t[i]);
    }return pa[t[cnt - 1]] > 0;
}void los(){
    cin >> n;
    for(int i = 1;i <= n;i ++){
        cin >> a[i]; int c = 0;
        while(a[i] % 2 == 0) c ++,a[i] /= 2;
        p[i] = {a[i],c};
    }cout << p[1].val() << " ";
    vector<num> c;
    c.push_back(p[1]);
    for(int i = 2;i <= n;i ++){
        sort(c.begin(),c.end()); vector<num> res;
        assert(c.size() <= 30);
        for(int j = -1;j < (int)c.size();j ++){
            int r = p[i].b; vector<num> tmp; ll sm = 0;
            for(int k = 0;k <= j;k ++)
                r += c[k].b,sm += c[k].a;
            for(int k = j + 1;k < c.size();k ++){
                if(c[k].b) tmp.emplace_back(c[k]);
                else sm += c[k].a;
            }if(r) tmp.emplace_back(p[i].a,r); else sm += p[i].a;
            tmp.emplace_back(sm,0);
            if(cmp(tmp,res)) res = tmp;
        }int x = 0;
        for(auto pp : res) x = (x + pp.val()) % mod;
        cout << x << " ",c = res;
    }cout << "\n";
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(cin >> T;T --;) los();
}