#include using namespace std; #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) #define ll long long const long long mod=998244353; const long long hmod=46216567629137; typedef int Vert; typedef int Capacity; typedef vector< vector > Layer; typedef vector< vector > Graph; // 「v からはじまる」「it~end の辺を使った」パスを作ってそこに流せるだけ流す Capacity dfs( Graph& G, Vert v, Layer::iterator it, Layer::iterator end, Capacity mf = numeric_limits::max() ) { if( it == end ) return mf; for(int i=0; i!=it->size(); ++i) if( G[v][(*it)[i]] ) if( Capacity f = dfs(G, (*it)[i], it+1, end, min(mf,G[v][(*it)[i]]) ) ) { G[v][(*it)[i]] -= f; G[(*it)[i]][v] += f; return f; } return 0; } Capacity dinic( Graph& G, int Src, int Dest ) { for( Capacity totalFlow = 0 ;; ) { // L[k] == Src から k ステップで行ける頂点の集合。BFSで求める。 Layer L(1); L.back() = vector(1,Src); vector reached(G.size()); reached[Src] = true; while( !reached[Dest] && !L.back().empty() ) { L.resize( L.size()+1 ); vector &l0=L[L.size()-2], &l1=L[L.size()-1]; for(int i=0; i!=l0.size(); ++i) for(Vert u=0; u!=G.size(); ++u) if( G[l0[i]][u] && !reached[u] ) l1.push_back(u), reached[u]=true; } L.back() = vector(1, Dest); // Dest までたどりつけなくなったので最大流の計算完了 if( !reached[Dest] ) return totalFlow; // たどりつける場合はDFSで流しまくる while( int f = dfs(G, Src, L.begin()+1, L.end()) ) totalFlow += f; } } int main(){ cin.tie(0)->sync_with_stdio(0); cout.tie(0); int T; cin>>T; for(int z=1;z<=T;z++){ ll A1,A2,A3,B1,B2,B3; cin>>A1>>A2>>A3>>B1>>B2>>B3; Graph g(8,vector(8)); g[0][1]=A1; g[0][2]=A2; g[0][3]=A3; g[1][4]=2e18; g[1][6]=2e18; g[2][4]=2e18; g[2][5]=2e18; g[3][5]=2e18; g[3][6]=2e18; g[4][7]=B1; g[5][7]=B2; g[6][7]=B3; ll all=A1+A2+A3; cout<(8)); g1[0][1]=A1; g1[0][2]=A2; g1[0][3]=A3; g1[1][5]=2e18; g1[2][6]=2e18; g1[3][4]=2e18; g1[4][7]=B1; g1[5][7]=B2; g1[6][7]=B3; cout<