#include <bits/stdc++.h>
using namespace std;
inline int read()
{
	char ch;
	while((ch=getchar())<'0'||ch>'9');
	int res=ch-'0';
	while((ch=getchar())>='0'&&ch<='9') res=res*10+ch-'0';
	return res;
}	
const int M=1001000;
const int V=2000000;
int prm[150100],tot,pim[M<<1];
void pre()
{
	pim[1]=1;
	for(int i=2;i<=V;i++)
	{
		if(!pim[i]) pim[i]=prm[++tot]=i;
		for(int j=1,tmp;j<=tot&&(tmp=prm[j]*i)<=V;j++)
		{
			pim[tmp]=prm[j];
			if(i%prm[j]==0) break;
		}
	}
}
int n,m,K,c[M<<1],a[M];
struct Tree{
	int d[M<<1];
	inline int lowbit(int x){ return x&-x; }
	void pre(){ for(int i=1;i<=m;i++) d[i]=1e9; }
	void upt(int x,int v)
	{
		for(int i=x;i<=m;i+=lowbit(i)) 
			d[i]=min(d[i],v);
	}
	int  qry(int x)
	{
		int res=1e9;
		for(int i=x;i;i-=lowbit(i)) res=min(res,d[i]);
		return res;
	}
}T;
int nn;
bool check(int x)
{
	int sum=0;
	for(int i=1;i<=nn;i++)
	{
		if(a[i]>x)
		{
			int tmp=a[i]/(x+1)+1;
			sum+=c[tmp];
			if(sum>K) break;
		}
	}
	return sum<=K;
}
int main()
{
	pre();
	int t=read();
	while(t--)
	{
		n=read();m=read();K=read();
		nn=(n+1)/2;
		for(int i=1;i<=n;i++) a[i]=read();
		sort(a+1,a+1+n);
		for(int i=1;i<=m;i++) c[i]=read();
		for(int i=1;i<=m;i++) c[i+m]=1e9;
		m<<=1;
		T.pre();
		c[1]=0;
		for(int i=1;i<=m;i++) T.upt(m+1-i,c[i]);
		for(int i=2;i<=m;i++)
		{
			c[i]=min(c[i],T.qry(m+1-pim[i])+T.qry(m+1-i/pim[i]));
			T.upt(m+1-i,c[i]);
		}
		for(int i=1;i<=m;i++) c[i]=T.qry(m+1-i);
		int L=0,R=a[nn];
		while(L<=R)
 		{
 			int mid=L+R>>1;
			if(check(mid)) R=mid-1;
			else L=mid+1;	
		}
		printf("%d\n",R+1);
	}
	return 0;
}