Bài toán dãy con chung dài nhất (LCS) là một bài toán nổi tiếng trong khoa học máy tính. Mọi sinh viên khoa học máy tính ở LQDOJ đều biết bài toán này. FOS cũng vậy.

Nhớ lại rằng một dãy con của một xâu \(S\) có được bằng cách xóa một số ký tự khỏi \(S\). Cho hai xâu \(S\) và \(T\), bài toán LCS là tìm xâu dài nhất là xâu con của cả \(S\) và \(T\).

FOS thích việc tìm ra những vấn đề khó hơn từ một vấn đề quen thuộc. Lần này, dựa trên vấn đề LCS, anh ấy đã nghĩ ra vấn đề sau:

Cho hai xâu \(S\) và \(T\), có bao nhiêu LCS phân biệt của \(S\) và \(T\)?. Viết một chương trình để giúp FOS giải quyết vấn đề này. Vì kết quả có thể rất lớn, bạn chỉ cần in phần còn lại của kết quả khi chia cho \(20030101\).

Input

• Dòng đầu tiên chứa số nguyên \(t\) (\(1 \leq t \leq 10\)), số lượng test case. Sau đó, có \(t\) nhóm dòng, mỗi nhóm dòng chứa 1 test case.
• Mỗi test case bao gồm hai dòng
  • dòng đầu tiên chứa xâu \(S\)
  • dòng thứ hai chứa xâu \(T\).
• Hai xâu chỉ bao gồm các ký tự viết thường và độ dài của mỗi xâu có tối đa \(1000\) ký tự.

Output

• Đối với mỗi trường hợp thử nghiệm, in một dòng duy nhất chứa hai số là độ dài của LCS và phần còn lại của số lượng LCS phân biệt của \(S\) và \(T\) khi chia lấy dư cho \(20030101\).

Example

2
acbd
acbd
fosfos
fos

4 1
3 1

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(1 \leq |S|,|T| \leq 20\)
• Subtask \(2\) (\(30\%\) số điểm): \(1 \leq |S|,|T| \leq 200\)
• Subtask \(3\) (\(20\%\) số điểm): \(1 \leq |S|,|T| \leq 1000\)

Nguồn: Bài 1 ngày 1 đề chọn ĐT HSG QG TP.ĐN 2022-2023