Cho một xâu ~s~ có độ dài ~n~ chỉ gồm các chữ cái latin thường. Định nghĩa một thao tác xoay xâu ~s~ là một thao tác biến xâu ~s_1s_2 \dots s_n~ thành ~s_ns_1 \dots s_{n - 1}~. Hay nói cách khác, là chuyển ký tự cuối cùng của ~s~ lên đầu xâu.

Gọi ~F_i~ là xâu ~s~ sau khi xoay được ~i~ thao tác.

Hỏi rằng trong đa tập gồm các xâu ~F_0, F_1, \dots, F_{n - 1}~, xâu ~F_0~ đứng thứ bao nhiêu về thứ tự từ điển (các xâu bằng nhau sẽ có thứ tự từ điển giống nhau).

Input Specification: Data taken from STRINGROT.INP

• Một dòng duy nhất chứa xâu ký tự ~s~.

Output Specification: Data written in STRINGROT.OUT

• Một dòng duy nhất là kết quả bài toán.

Subtasks

• Subtask #1 [20%]: Xâu ~s~ có độ dài không quá ~100~ ký tự.
• Subtask #2 [20%]: Xâu ~s~ có độ dài không quá ~1000~ ký tự.
• Subtask #3 [20%]: Xâu ~s~ có độ dài không quá ~10000~ ký tự.
• Subtask #4 [20%]: Xâu ~s~ có độ dài không quá ~100000~ ký tự.
• Subtask #5 [20%]: Xâu ~s~ có độ dài không quá ~1000000~ ký tự.

Sample Cases

Input #1:

bca

Output #1:

2

Explanation #1:

• Ta có ~F_0 = \text{bca}; F_1 = \text{abc}~. Do đó ~F_0~ đứng thứ hai về thứ tự từ điển.

Input #2:

baba

Output #2:

3

Explanation #2:

• Ta có ~F_0 = \text{baba}; F_1 = \text{abab}; F_2 = \text{baba}; F_3 = \text{abab}~. Do đó ~F_0~ đứng thứ ba về thứ tự từ điển.