#include <iostream>
using namespace std;
using ll = long long;
const ll N = 18;
#define rep(i, l, r) for(ll i = l; i <= r; i++)
ll T, K;
ll h[30];
bool check(ll H){
ll cnt = 0;
rep(i, 1, N) cnt += 2 * min(h[i], H);
return cnt <= K;
}
int main() {
cin >> T;
while(T--){
cin >> K;
rep(i, 1, N) cin >> h[i];
ll l = 0, r = 1e12;
while( l < r ){
ll mid = (l+r+1) >> 1;
if( check(mid) ){
l = mid;
}
else r = mid - 1;
}
cout << l << '\n';
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdXNpbmcgbGwgPSBsb25nIGxvbmc7CmNvbnN0IGxsIE4gPSAxODsKCiNkZWZpbmUgcmVwKGksIGwsIHIpIGZvcihsbCBpID0gbDsgaSA8PSByOyBpKyspCgpsbCBULCBLOwpsbCBoWzMwXTsKCmJvb2wgY2hlY2sobGwgSCl7CiAgICBsbCBjbnQgPSAwOwogICAgcmVwKGksIDEsIE4pIGNudCArPSAyICogbWluKGhbaV0sIEgpOwogICAgcmV0dXJuIGNudCA8PSBLOwp9CgppbnQgbWFpbigpIHsKICAgIGNpbiA+PiBUOwogICAgd2hpbGUoVC0tKXsKICAgICAgICBjaW4gPj4gSzsKICAgICAgICByZXAoaSwgMSwgTikgY2luID4+IGhbaV07CiAgICAgICAgCiAgICAgICAgbGwgbCA9IDAsIHIgPSAxZTEyOwogICAgICAgIHdoaWxlKCBsIDwgciApewogICAgICAgICAgICBsbCBtaWQgPSAobCtyKzEpID4+IDE7CiAgICAgICAgICAgIAogICAgICAgICAgICBpZiggY2hlY2sobWlkKSApewogICAgICAgICAgICAgICAgbCA9IG1pZDsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlIHIgPSBtaWQgLSAxOwogICAgICAgIH0KICAgICAgICAKICAgICAgICBjb3V0IDw8IGwgPDwgJ1xuJzsKICAgIH0KICAgIAogICAgcmV0dXJuIDA7Cn0=