Cho một xâu \(S\) có độ dài \(N\) chỉ chứa các ký tự latin in thường. Ký tự thứ \(x\) của xâu \((1\le x\le N)\) là \(S_x\).

Với mỗi giá trị \(i=1,2,3,...,N-1\), hãy tìm số nguyên không âm \(l\) lớn nhất sao cho:

• \(l+i\le N\), và
• \(S_k\ne S_{k+i}\) với mọi \(1\le k\le l\).

Lưu ý rằng \(l=0\) luôn thỏa hai điều kiện trên bất kể giá trị của \(i\).

Input

• Dòng đầu chứa số nguyên dương \(N\) \((2\le N\le 5000)\).
• Dòng tiếp theo chứa xâu \(S\) độ dài \(N\) chỉ gồm các ký tự latin in thường.

Output

• In ra \(N-1\) dòng là kết quả tương ứng với từng giá trị \(i\).

Ví dụ

Sample input 01

6
abccba

Sample output 01

2
4
1
2
0

Giải thích

• Với \(i=1\), ta có \(S_1\ne S_2\), \(S_2\ne S_3\), nhưng \(S_3=S_4\) nên câu trả lời là \(l=2\).
• Với \(i=2\), ta có \(S_1\ne S_3\), \(S_2\ne S_4\), \(S_3\ne S_5\), \(S_4\ne S_6\) nên câu trả lời là \(l=4\).
• Với \(i=3\), ta có \(S_1\ne S_4\), nhưng \(S_2=S_5\) nên câu trả lời là \(l=1\).
• Với \(i=4\), ta có \(S_1\ne S_5\), \(S_2\ne S_6\) nên câu trả lời là \(l=2\).
• Với \(i=5\), ta có \(S_1=S_6\) nên câu trả lời là \(l=0\).