Như các bạn đã biết, mọi số nguyên \(n, |n| > 1\) đều có thể biểu diễn dưới dạng tích các số nguyên tố. Không chỉ vậy, các số hữu tỉ cũng có thể biểu diễn được dưới dạng này, nếu như ta coi phép chia có vai trò tương tự như phép nhân. Ví dụ:

Bài toán trước đây đơn giản khi yêu cầu bạn nhân và chia hai số duy nhất dưới dạng phân tích thừa số nguyên tố (TSNT). Hôm nay, độ khó được nâng lên: bạn phải thực hiện việc nhân và chia đến \(T = 1000\) lần.

Liệu code của bạn có đủ tối ưu để giải bài toán này? Chúc may mắn!

Input

• Dòng đầu tiên chứa số nguyên \(T\) (\(T = 1000\)) là số lượng truy vấn.
• Tiếp theo là \(T\) nhóm truy vấn, mỗi nhóm gồm 4 dòng:
• Dòng đầu tiên chứa số nguyên \(n_x\): số lượng TSNT của số \(x\).
• Dòng thứ hai chứa \(n_x\) cặp số \(a_i, b_i\) với ý nghĩa \(x = a_1^{b_1} \cdot a_2^{b_2} \cdot \cdots \cdot a_{n_x}^{b_{n_x}}\).
• Dòng thứ ba chứa số nguyên \(n_y\): số lượng TSNT của số \(y\).
• Dòng thứ tư chứa \(n_y\) cặp số \(c_j, d_j\) với ý nghĩa \(y = c_1^{d_1} \cdot c_2^{d_2} \cdot \cdots \cdot c_{n_y}^{d_{n_y}}\).

Output

• Gồm \(2 \cdot T\) nhóm kết quả, mỗi nhóm gồm 2 dòng:
• Dòng đầu tiên chứa số nguyên \(n\) và các cặp thừa số, số mũ biểu diễn giá trị \(x \times y\) theo định dạng đã cho.
• Dòng thứ hai chứa số nguyên \(n\) và các cặp thừa số, số mũ biểu diễn giá trị \(x / y\) theo định dạng đã cho.

Ràng buộc

• \(1 \leq n_x, n_y \leq 100\).
• \(a_i, c_j\) là các số nguyên tố \(\leq 10^6 + 500\).
• \(b_i, d_j\) là các số nguyên dương, \(1 \leq b_i, d_j \leq 10^6\).
• Các dãy \(a\) và \(c\) đều tăng nghiêm ngặt.
• \(x \neq y\).

Ví dụ

Input

1
3
2 2 3 1 5 1
1
5 2

Output

3
2 2 3 1 5 3
3
2 2 3 1 5 -1

Input

2
2
2 3 5 2
2
3 1 7 4
3
2 1 3 2 5 1
2
3 3 5 2

Output

3
2 3 3 1 5 2 7 4
4
2 3 3 -1 5 2 7 -4
3
2 1 3 5 5 3
2
2 1 3 -1 5 -1

Giải thích

• Truy vấn 1:
• \(x = 2^3 \cdot 5^2\) và \(y = 3^1 \cdot 7^4\).
• \(x \times y = 2^3 \cdot 3^1 \cdot 5^2 \cdot 7^4\).
• \(x / y = 2^3 \cdot 3^{-1} \cdot 5^2 \cdot 7^{-4}\).
• Truy vấn 2:
• \(x = 2^1 \cdot 3^2 \cdot 5^1\) và \(y = 3^3 \cdot 5^2\).
• \(x \times y = 2^1 \cdot 3^5 \cdot 5^3\).
• \(x / y = 2^1 \cdot 3^{-1} \cdot 5^{-1}\).