Chu Kỳ Của Các Tiền Tố

Với một xâu $S$, tiền tố dài $i$ được gọi là tuần hoàn nếu nó bằng một xâu ngắn hơn lặp lại nguyên số lần, và số lần lặp ít nhất là $2$. Bạn cần xử lý nhiều testcase và liệt kê mọi tiền tố tuần hoàn của từng xâu.

Input

• Dòng đầu chứa số nguyên $T$.
• Mỗi testcase gồm một dòng chứa $n$, tiếp theo là một dòng chứa xâu $S$ có đúng $n$ ký tự.

Output

• Với testcase thứ $x$, trước hết in dòng Test case #x. Sau đó, với mỗi tiền tố tuần hoàn theo thứ tự độ dài tăng dần, in một dòng gồm độ dài tiền tố và số lần lặp. In thêm một dòng trống sau mỗi testcase.

Constraints

• $1\le T\le 20$.
• $2\le n\le 10^6$ cho mỗi testcase.
• Tổng các giá trị $n$ không vượt quá $10^6$.
• Mỗi xâu chỉ gồm các chữ cái thường tiếng Anh.

Scoring

• Subtask $1$ ($50\%$ số điểm): Tổng các giá trị $n$ không vượt quá $200$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

1
6
ababab

Test case #1
4 2
6 3