Cho một xâu ~S~ có độ dài ~n \le 5*10^5~ gồm các chữ cái tiếng Anh in thường.

Một xâu tiền tố của xâu ~S~ được gọi là đẹp nếu nó bằng với xâu hậu tố tương ứng với nó. Hay nói cách khác, tiền tố độ dài ~L~ có dạng ~S[1,2,...,L]~ phải bằng với hậu tố độ dài ~L~ có dạng ~S[n-L+1,n-L+2,...,n]~.

Do việc tìm tất cả các xâu tiền tố đẹp là một công việc khá dễ dàng, nên Tí muốn giao thêm cho các bạn một công việc nữa, đó là với mỗi xâu tiền tố đẹp, hãy đếm xem có bao nhiêu xâu con liên tiếp trong ~S~ bằng với tiền tố đó.

Input

Dòng đầu gồm số nguyên dương ~n~ (~n \le 5*10^5~) miêu tả độ dài của xâu ~S~.

Dòng thứ hai miêu tả xâu ~S~.

Output

Dòng đầu tiên in ra số nguyên dương ~m~ là số lượng xâu tiền tố đẹp.

~m~ dòng sau, mỗi dòng in ra hai số nguyên dương ~u_i~ ~v_i~, với ~u_i~ là độ dài của xâu tiền tố đẹp tìm được, và ~v_i~ là số lần xuất hiện của nó.

Hãy in ra các cặp ~u_i~ ~v_i~ theo thứ tự tăng dần của ~u_i~.

Sample Input 1

7
abacaba

Sample Output 1

3
1 4
3 2
7 1

Sample Input 2

4
aaaa

Sample Output 2

4
1 4
2 3
3 2
4 1