Trong một bài kiểm tra 15 phút môn Hóa, giáo viên cho đề như sau: Cho \(K\) phương trình hóa học, em hãy cân bằng tất cả phương trình hóa học đã cho. Mỗi phương trình hóa học gồm 2 chất phản ứng và có 1 hoặc 2 chất sản phẩm tùy thuộc vào phương trình hóa học đó.

Input

• Dòng 1: Số lượng truy vấn (\(K \le 100\)).
• Trong \(K\) dòng tiếp theo, hãy nhập 2 chất tham gia và sản phẩm của 2 chất tham gia (sản phẩm có thể là 1 hoặc 2 chất).

Output

• Lần lượt là hệ số của \(K\) phương trình hóa học.

Example

2
Fe O2 Fe2O3
Al O2 Al2O3

4 3 2
4 3 2