#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e6+5;
 
int n, a[maxN], b[maxN];
 
void solve()
{
	int x = 1, y = 1, ans = 0;
	for(int i=1; i<=n; i+=1)
	{
		cout<<x<<'\n';
		if(__gcd(x, a[i]) == x)
		{
			ans++;
		}
		x = __gcd(x,a[i]);
	}
	cout<<ans<<'\n';
}
 
int main() {
	int test = 1;
	cin>>test;
	while(test--)
	{
		cin>>n;
		for(int i=1; i<=n; i+=1) cin>>a[i];
		for(int i=1; i<=n; i+=1) cin>>b[i];
		solve();
	}
	return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmNvbnN0IGludCBtYXhOID0gMWU2KzU7CgppbnQgbiwgYVttYXhOXSwgYlttYXhOXTsKCnZvaWQgc29sdmUoKQp7CglpbnQgeCA9IDEsIHkgPSAxLCBhbnMgPSAwOwoJZm9yKGludCBpPTE7IGk8PW47IGkrPTEpCgl7CgkJY291dDw8eDw8J1xuJzsKCQlpZihfX2djZCh4LCBhW2ldKSA9PSB4KQoJCXsKCQkJYW5zKys7CgkJfQoJCXggPSBfX2djZCh4LGFbaV0pOwoJfQoJY291dDw8YW5zPDwnXG4nOwp9CgppbnQgbWFpbigpIHsKCWludCB0ZXN0ID0gMTsKCWNpbj4+dGVzdDsKCXdoaWxlKHRlc3QtLSkKCXsKCQljaW4+Pm47CgkJZm9yKGludCBpPTE7IGk8PW47IGkrPTEpIGNpbj4+YVtpXTsKCQlmb3IoaW50IGk9MTsgaTw9bjsgaSs9MSkgY2luPj5iW2ldOwoJCXNvbHZlKCk7Cgl9CglyZXR1cm4gMDsKfQ==

MQo3CjEgMiAzIDQgNSA2IDcKMSAyIDMgNCA1IDYgNwozCjY3IDY3IDY3CjY3IDY3IDY3CjYKOCAxMCAxMCAxMiAxMiAxNAo4IDEwIDEwIDEyIDEyIDE0CjgKMiA0IDggMTYgMzIgNjQgMTI4IDI1NgoyIDQgOCAxNiAzMiA2NCAxMjggMjU2Cg==

1
7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
3
67 67 67
67 67 67
6
8 10 10 12 12 14
8 10 10 12 12 14
8
2 4 8 16 32 64 128 256
2 4 8 16 32 64 128 256