#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define in(a, b) for (ll i = (a); i <= (b); i++)                // in using i
#define inj(a, b) for (ll j = (a); j <= (b); j++)               // in using j
#define ink(a, b) for (ll k = (a); k <= (b); k++)               // in using k
#define inl(a, b) for (ll l = (a); l <= (b); l++)               // in using l
#define inr(a, b) for(ll i = (a); i >= (b); i--)                // in reverse
#define inrj(a, b) for(ll j = (a); j >= (b); j--)                // in reverse
#define inrk(a, b) for(ll k = (a); k >= (b); k--)                // in reverse
#define inrl(a, b) for(ll l = (a); l >= (b); l--)                // in reverse
#define tt ll tcs; cin>>tcs; while(tcs--)                       // include test cases
#define ina(arr,n) ll arr[(n+1)]={0}; in(1,n) cin>>arr[i]       // input arr of n elements
#define inv(vec,n) vector<ll> vec(n+1); vec[0]=0; in(1,n) cin>>vec[i]; // input vector of n elements
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define pll pair <ll,ll>
#define vpll vector <pll>
#define sll set <ll>
#define vll vector<ll>
#define mll map <ll,ll>
#define all(x) x.begin(), x.end()
const ll mod=1e9+7;
#define vvll vector<vll>
#define pref(p,a,n) vll p(n+1); in(1,n) p[i]=p[i-1]+a[i];
#define vec2(a,n,m) vvll a(n+1,vll(m+1))
// #define vec2(a,n,m,val) vvll a(n+1,vll(m+1,val))

#define vec3(a,l,m,n) vector<vvll>a(l+1,vvll(m+1,vll(n+1)));
// #define vec3(a,l,m,n,val) vector<vvll>a(l+1,vvll(m+1,vll(n+1,val)));
# define FAST ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

int main(){
    FAST
    tt{
        ll n,m,k;
        cin>>n>>m>>k;
        inv(a,n);
        inv(cst,m);
        inr(m-1,1){
            cst[i]=min(cst[i],cst[i+1]);
        }
        cst.push_back(1e17);
        cst[1]=0;
        multiset<ll>future;
        future.insert(1e17);
        vvll vals(m+2);

        for(ll i=2;i<=(m+1);i++){
            if(i==(m+1)){
                int t=1;
            }
            cst[i]=min(cst[i],*future.begin());
            for(ll j=2*i;j<=i*i;j+=i){
                ll nv=cst[i]+cst[j/i];
                if(j>m){
                    future.insert(nv);
                    break;
                }
                vals[j].push_back(nv);
                future.insert(nv);
            }
            for(auto x:vals[i]){
                future.erase(future.find(x));
            }
        // cout<<"DONE"<<i<<endl;

        }

        // in(1,m){
        //     cout<<cst[i]<<' ';
        // }
        // cout<<endl;

        ll lo=0;
        ll hi=m;
        auto ok=[&](ll md)->bool{
            //can i make more than equal to (n)/2 elements less than equal to md
            vll cc;
            in(1,n){
                    // ll x=(a[i]+md-1)/md;
                    ll x=(a[i]/(md+1))+1;
                    cc.push_back(cst[x]);
            }

            sort(all(cc));
            ll tcst=0;
            for(int i=0;i<((n+1)/2);i++){
                tcst+=cc[i];
            }
            return (tcst<=k);
        }
        ;
        // ok(3);
        ll ans=m;

        while(lo<=hi){
            ll mid=(lo+hi)/2;
            if(ok(mid)){
                ans=mid;hi=mid-1;
            }
            else{
                lo=mid+1;
            }
        }
        cout<<ans<<endl;
    }
}