/*__ _(_) __ _ ___ ___ _ _ __| | __ _ _ _| |_ ___
/ _` | |/ _` |/ _ \/ __| | | |/ _` |/ _` | | | | __/ _ \
| (_| | | (_| | (_) \__ \ |_| | (_| | (_| | |_| | || (_) |
\__, |_|\__,_|\___/|___/\__,_|\__,_|\__,_|\__,_|\__\___/
|___/ Accepted Code */
#include <bits/stdc++.h>
using namespace std;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
bool ok=false;
scanf("%d",&n);
vector<int> a;
for(int i=0; i<n; i++)
{
int x;
scanf("%d",&x);
a.push_back(x);
}
for(int i=n; i<4; i++) a.push_back(0);
int r[4];
memset(r,0,sizeof(r));
for(int i=0; i<n; i++)
scanf("%d",r+i);
ok=true;
for(int i=0; i<n; i++)
if(a[i]!=r[i]) ok=false;
if(ok)
{
printf("%d\n",0);
continue;
}
int8_t exist[50][50][50][50];
memset(exist,0,sizeof(exist));
queue<vector<int>> lq;
for(lq.push(a), exist[a[0]][a[1]][a[2]][a[3]]=1; !lq.empty(); lq.pop())
{
vector<int> cur=lq.front();
//Do nuoc tu i sang j
vector<int> w;
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
if(i!=j && cur[i]<=a[j]-cur[j])
{
// Tien hanh do
w=cur;
w[j]+=w[i];
w[i]=0;
// kiem tra da thoa man chua?
ok=true;
for(int k=0; k<n; k++)
if(r[k]!=w[k])
{
ok=false;
break;
}
// Neu da thao man roi
if(ok)
{
printf("%d\n",exist[cur[0]][cur[1]][cur[2]][cur[3]]);
break;
}
if(exist[w[0]][w[1]][w[2]][w[3]]==0)
{
exist[w[0]][w[1]][w[2]][w[3]]=exist[cur[0]][cur[1]][cur[2]][cur[3]]+1;
lq.push(w);
}
}
if(ok) break;
}
if(ok) break;
// Do day binh j bang nuoc tu i;
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
if(i!=j && cur[j]!=a[j] && cur[i]>a[j]-cur[j])
{
w=cur;
w[i]=cur[i]-(a[j]-cur[j]);
w[j]=a[j];
// kiem tra da thoa man chua?
ok=true;
for(int k=0; k<n; k++)
if(r[k]!=w[k])
{
ok=false;
break;
}
// Neu da thao man roi
if(ok)
{
printf("%d\n",exist[cur[0]][cur[1]][cur[2]][cur[3]]);
break;
}
if(exist[w[0]][w[1]][w[2]][w[3]]==0)
{
exist[w[0]][w[1]][w[2]][w[3]]=exist[cur[0]][cur[1]][cur[2]][cur[3]]+1;
lq.push(w);
}
}
if(ok) break;
}
if(ok) break;
//Do nuoc ra cong.
for(int i=0; i<n; i++)
if(cur[i]>0)
{
w=cur;
w[i]=0;
// kiem tra da thoa man chua?
ok=true;
for(int k=0; k<n; k++)
if(r[k]!=w[k])
{
ok=false;
break;
}
// Neu da thao man roi
if(ok)
{
printf("%d\n",exist[cur[0]][cur[1]][cur[2]][cur[3]]);
break;
}
if(exist[w[0]][w[1]][w[2]][w[3]]==0)
{
exist[w[0]][w[1]][w[2]][w[3]]=exist[cur[0]][cur[1]][cur[2]][cur[3]]+1;
lq.push(w);
}
}
if(ok) break;
}
if(lq.empty()) printf("NO\n");
}
return 0;
}
LypfXyBfKF8pIF9fIF8gIF9fXyAgX19fIF8gICBfICBfX3wgfCBfXyBfIF8gICBffCB8XyBfX18gIAogLyBfYCB8IHwvIF9gIHwvIF8gXC8gX198IHwgfCB8LyBfYCB8LyBfYCB8IHwgfCB8IF9fLyBfIFwgCnwgKF98IHwgfCAoX3wgfCAoXykgXF9fIFwgfF98IHwgKF98IHwgKF98IHwgfF98IHwgfHwgKF8pIHwKIFxfXywgfF98XF9fLF98XF9fXy98X19fL1xfXyxffFxfXyxffFxfXyxffFxfXyxffFxfX1xfX18vIAogfF9fXy8gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgQWNjZXB0ZWQgQ29kZSAgKi8KI2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWFpbigpCnsKICAgIGludCBUOwogICAgc2NhbmYoIiVkIiwmVCk7CiAgICB3aGlsZShULS0pCiAgICB7CiAgICAgICAgaW50IG47CiAgICAgICAgYm9vbCBvaz1mYWxzZTsKICAgICAgICBzY2FuZigiJWQiLCZuKTsKCiAgICAgICAgdmVjdG9yPGludD4gYTsKICAgICAgICBmb3IoaW50IGk9MDsgaTxuOyBpKyspCiAgICAgICAgewogICAgICAgICAgICBpbnQgeDsKICAgICAgICAgICAgc2NhbmYoIiVkIiwmeCk7CiAgICAgICAgICAgIGEucHVzaF9iYWNrKHgpOwogICAgICAgIH0KICAgICAgICBmb3IoaW50IGk9bjsgaTw0OyBpKyspIGEucHVzaF9iYWNrKDApOwoKICAgICAgICBpbnQgcls0XTsKICAgICAgICBtZW1zZXQociwwLHNpemVvZihyKSk7CiAgICAgICAgZm9yKGludCBpPTA7IGk8bjsgaSsrKQogICAgICAgICAgICBzY2FuZigiJWQiLHIraSk7CgogICAgICAgIG9rPXRydWU7CiAgICAgICAgZm9yKGludCBpPTA7IGk8bjsgaSsrKQogICAgICAgICAgICBpZihhW2ldIT1yW2ldKSBvaz1mYWxzZTsKICAgICAgICBpZihvaykKICAgICAgICB7CiAgICAgICAgICAgIHByaW50ZigiJWRcbiIsMCk7CiAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgIH0KCiAgICAgICAgaW50OF90IGV4aXN0WzUwXVs1MF1bNTBdWzUwXTsKICAgICAgICBtZW1zZXQoZXhpc3QsMCxzaXplb2YoZXhpc3QpKTsKCiAgICAgICAgcXVldWU8dmVjdG9yPGludD4+IGxxOwoKICAgICAgICBmb3IobHEucHVzaChhKSwgZXhpc3RbYVswXV1bYVsxXV1bYVsyXV1bYVszXV09MTsgIWxxLmVtcHR5KCk7IGxxLnBvcCgpKQogICAgICAgIHsKICAgICAgICAgICAgdmVjdG9yPGludD4gY3VyPWxxLmZyb250KCk7CiAgICAgICAgICAgIC8vRG8gbnVvYyB0dSBpIHNhbmcgagogICAgICAgICAgICB2ZWN0b3I8aW50PiB3OwogICAgICAgICAgICBmb3IoaW50IGk9MDsgaTxuOyBpKyspCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGZvcihpbnQgaj0wOyBqPG47IGorKykKICAgICAgICAgICAgICAgICAgICBpZihpIT1qICYmIGN1cltpXTw9YVtqXS1jdXJbal0pCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAvLyBUaWVuIGhhbmggZG8KICAgICAgICAgICAgICAgICAgICAgICAgdz1jdXI7CiAgICAgICAgICAgICAgICAgICAgICAgIHdbal0rPXdbaV07CiAgICAgICAgICAgICAgICAgICAgICAgIHdbaV09MDsKICAgICAgICAgICAgICAgICAgICAgICAgLy8ga2llbSB0cmEgZGEgdGhvYSBtYW4gY2h1YT8KICAgICAgICAgICAgICAgICAgICAgICAgb2s9dHJ1ZTsKICAgICAgICAgICAgICAgICAgICAgICAgZm9yKGludCBrPTA7IGs8bjsgaysrKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYocltrXSE9d1trXSkKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBvaz1mYWxzZTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICAgLy8gTmV1IGRhIHRoYW8gbWFuIHJvaQogICAgICAgICAgICAgICAgICAgICAgICBpZihvaykKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgcHJpbnRmKCIlZFxuIixleGlzdFtjdXJbMF1dW2N1clsxXV1bY3VyWzJdXVtjdXJbM11dKTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIGlmKGV4aXN0W3dbMF1dW3dbMV1dW3dbMl1dW3dbM11dPT0wKQogICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBleGlzdFt3WzBdXVt3WzFdXVt3WzJdXVt3WzNdXT1leGlzdFtjdXJbMF1dW2N1clsxXV1bY3VyWzJdXVtjdXJbM11dKzE7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBscS5wdXNoKHcpOwoKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGlmKG9rKSBicmVhazsKICAgICAgICAgICAgfQogICAgICAgICAgICBpZihvaykgYnJlYWs7CiAgICAgICAgICAgIC8vIERvIGRheSBiaW5oIGogYmFuZyBudW9jIHR1IGk7CiAgICAgICAgICAgIGZvcihpbnQgaT0wOyBpPG47IGkrKykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgZm9yKGludCBqPTA7IGo8bjsgaisrKQogICAgICAgICAgICAgICAgICAgIGlmKGkhPWogJiYgY3VyW2pdIT1hW2pdICYmIGN1cltpXT5hW2pdLWN1cltqXSkKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIHc9Y3VyOwogICAgICAgICAgICAgICAgICAgICAgICB3W2ldPWN1cltpXS0oYVtqXS1jdXJbal0pOwogICAgICAgICAgICAgICAgICAgICAgICB3W2pdPWFbal07CiAgICAgICAgICAgICAgICAgICAgICAgIC8vIGtpZW0gdHJhIGRhIHRob2EgbWFuIGNodWE/CiAgICAgICAgICAgICAgICAgICAgICAgIG9rPXRydWU7CiAgICAgICAgICAgICAgICAgICAgICAgIGZvcihpbnQgaz0wOyBrPG47IGsrKykKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmKHJba10hPXdba10pCiAgICAgICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgb2s9ZmFsc2U7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIC8vIE5ldSBkYSB0aGFvIG1hbiByb2kKICAgICAgICAgICAgICAgICAgICAgICAgaWYob2spCiAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHByaW50ZigiJWRcbiIsZXhpc3RbY3VyWzBdXVtjdXJbMV1dW2N1clsyXV1bY3VyWzNdXSk7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICBpZihleGlzdFt3WzBdXVt3WzFdXVt3WzJdXVt3WzNdXT09MCkKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgZXhpc3Rbd1swXV1bd1sxXV1bd1syXV1bd1szXV09ZXhpc3RbY3VyWzBdXVtjdXJbMV1dW2N1clsyXV1bY3VyWzNdXSsxOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgbHEucHVzaCh3KTsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGlmKG9rKSBicmVhazsKICAgICAgICAgICAgfQogICAgICAgICAgICBpZihvaykgYnJlYWs7CgogICAgICAgICAgICAvL0RvIG51b2MgcmEgY29uZy4KICAgICAgICAgICAgZm9yKGludCBpPTA7IGk8bjsgaSsrKQogICAgICAgICAgICAgICAgaWYoY3VyW2ldPjApCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgdz1jdXI7CiAgICAgICAgICAgICAgICAgICAgd1tpXT0wOwogICAgICAgICAgICAgICAgICAgIC8vIGtpZW0gdHJhIGRhIHRob2EgbWFuIGNodWE/CiAgICAgICAgICAgICAgICAgICAgb2s9dHJ1ZTsKICAgICAgICAgICAgICAgICAgICBmb3IoaW50IGs9MDsgazxuOyBrKyspCiAgICAgICAgICAgICAgICAgICAgICAgIGlmKHJba10hPXdba10pCiAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIG9rPWZhbHNlOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAvLyBOZXUgZGEgdGhhbyBtYW4gcm9pCiAgICAgICAgICAgICAgICAgICAgaWYob2spCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICBwcmludGYoIiVkXG4iLGV4aXN0W2N1clswXV1bY3VyWzFdXVtjdXJbMl1dW2N1clszXV0pOwogICAgICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgaWYoZXhpc3Rbd1swXV1bd1sxXV1bd1syXV1bd1szXV09PTApCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICBleGlzdFt3WzBdXVt3WzFdXVt3WzJdXVt3WzNdXT1leGlzdFtjdXJbMF1dW2N1clsxXV1bY3VyWzJdXVtjdXJbM11dKzE7CiAgICAgICAgICAgICAgICAgICAgICAgIGxxLnB1c2godyk7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICBpZihvaykgYnJlYWs7CiAgICAgICAgfQogICAgICAgIGlmKGxxLmVtcHR5KCkpIHByaW50ZigiTk9cbiIpOwogICAgfQogICAgcmV0dXJuIDA7Cn0K