Chào mừng bạn đến với chương C của giáo án, trong chương này, nhà nghiên cứu nổi tiếng của trường đại học Harvát P. sẽ giới thiệu đến bạn cách khen crush của mình sao cho đúng.

Bạn sẽ rất ngượng ngùng khi khen crush (hoặc chỉ có P. là như vậy), cho nên, để khen crush, bạn sẽ sử dụng một kĩ thuật mã hoá tiên tiến đó chính là dùng xâu để chèn thông điệp vào đó.

Cụ thể như sau, gọi tên của crush bạn là một xâu $s$ thì một đoạn thông điệp sẽ là $s + cute$ (vd: $s$ = "huunguyen" thì thông điệp sẽ là "huunguyencute"), đoạn mật mã đã được mã hoá sẽ là một xâu $t$. Nhiệm vụ của bạn đơn giản là đếm số lượng thông điệp nhiều nhất có sẵn trong xâu mã hoá đó và ngoài ra, nếu như thay đổi vị trí các kí tự trong xâu $t$ một cách tối ưu nhất thì sẽ có tối đa bao nhiêu đoạn thông điệp. Lưu ý ở đây các thông điệp không được chồng lên nhau. $^{(1)}$

Ngoài ra, vì P. là một người chu toàn nên khi đưa ra nghiên cứu, P. đã chia nghiên cứu ra thành một số phần nhỏ, cụ thể, P. đưa ra $n$ câu hỏi với mỗi câu hỏi có dạng như $^{(1)}$, bạn cần phải hoàn thành hết các câu hỏi này để vượt qua bài kiểm tra của chương C.

Input

• Dòng đầu tiên gồm số nguyên $n$ - số lượng câu hỏi trong nghiên cứu của nhà khoa học P. giấu tên. $(1\leq n\leq 10)$
• $n$ dòng tiếp theo mỗi dòng chứa hai xâu kí tự $s$ và $t$ lần lượt là tên của crush bạn và xâu mã hoá, dữ liệu đảm bảo tổng độ dài của $t$ trong $n$ câu hỏi không vượt quá $2.10^5$, $s$ và $t$ không chứa kí tự trống và chỉ chứa những kí tự latin thường ('a'...'z').

Output

• Gồm $n$ dòng với dòng thứ $i$ là đáp án cho câu hỏi thứ $i$ gồm hai số nguyên lần lượt là số lượng thông điệp nhiều nhất có thể đếm trong xâu $t$ và số lượng thông điệp tối đa có thể có nếu ta thay đổi xâu $t$.

Subtasks

• Subtask 1: Đảm bảo tổng độ dài của $t$ trong $n$ câu hỏi không vượt quá $2000$. (100 điểm)
• Subtask 2: Không có ràng buộc gì thêm. (100 điểm)

Examples

1
huunguyen huunguyencuteetcuhunuguyen

1 2

1
cute cutecutecute

1 1