Chán với phép cộng và nhân phân số thông thường, Bảo Châu nghiên cứu thêm về xâu. Cô ấy nhận thấy khi lặp lại liên tiếp n lần xâu S ta được 1 xâu S₁, và cô ấy gọi S₁ được gọi là lũy thừa bậc n của xâu S, khi đó xâu S được gọi là xâu cơ sở của xâu S₁.

Bảo Châu muốn tim xâu cơ sở dài nhất trong bài toán sau: Cho hai xâu S₁ và S₂, hãy xác định xâu Q là xâu cơ sở dài nhất của S₁ và S_2.

Dữ liệu:

• Dòng đầu tiên ghi xâu S₁.
• Dòng thứ hai ghi xâu S₂.

Kết quả: Đưa ra xâu cơ sở chung dài nhất. Dữ liệu đảm bảo luôn tồn tại kết quả.

Độ dài các xâu không vượt quá 10⁶