1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>
using namespace std;
using lld = long long;

struct Number{
	int n;
	vector<int> t;

	Number(int x=0): n(x), t(x,0) {}

	int& operator [] (const int x){
		return t[x];
	}

	const int& operator [] (const int x) const {
		return t[x];
	}
};

istream& operator >> (istream& in, Number& x){
	in >> x.n;
	x.t.resize(x.n);
	for(int& i : x.t)
		in >> i;
	return in;
}

ostream& operator << (ostream& out, const Number& x){
	out << x.n;
	for(int i : x.t)
		cout << " " << i;
	return out;
}

Number operator * (const Number& a, const Number& b){
	lld sa=0, sb=0;
	lld x,y,z;

	vector<lld> f(90);
	f[0] = 1, f[1] = 2;
	for(int i=2;i<90;i++)
		f[i] = f[i-1]+f[i-2];

	for(int i=0;i<a.n;i++)
		if(a[i] == 1)
			sa += f[i];

	x = y = 1;
	for(int i=0;i<b.n;i++)
		if(b[i] == 1)
			sb += f[i];

	lld s = sa*sb;
	Number c(90);
	for(int i=89;i>=0;i--)
		if(s >= f[i])
			c[i] = 1, s -= f[i];

	while(c.t.size() >= 1 && c.t.back() == 0)
		c.t.pop_back(), c.n--;

	return c;
}

void query(void){
	Number x,y;

	cin >> x >> y;
	cout << x*y << "\n";
}

int main(void){
	ios_base::sync_with_stdio(false);	
	cin.tie(NULL);

	int q;
	cin >> q;

	while(q--)
		query();

	return 0;
}