A long time ago, in a certain Dmojistan far far away, there existed a small DMOPC committee of ~N~ people. One fateful day, when the ~N~ members were sitting in a circle (with the ~i~-th member sitting next to the ~(i+1)~-th for all ~1 \le i < N~ and the ~N~-th member sitting next to the first) discussing new problem ideas, an evil witch appeared and stated the following: "Look to your left and to your right. By the beginning of next year, at least one of those people will be gone". Terrified about the legitimacy of her statement, the DMOPC committee banded together and wondered: if what the witch said was true, at most how many members will remain in the committee next year? Your job is to answer this question and provide an example of an optimal scenario.

Constraints

~3 \le N \le 2 \times 10^5~

Subtask 1 [20%]

~3 \le N \le 6~

Subtask 2 [80%]

No additional constraints.

Input Specification

The first and only line contains a single integer ~N~.

Output Specification

On the first line output an integer ~M~, representing the maximum number of people that can remain in the committee next year.

On the second line output a string of length ~N~ consisting of the characters _ and M. This string should represent an optimal scenario in which the ~N~ members used to sit in a circle and ~M~ people remain in the committee. Specifically, the ~i~-th character of the string should be M if the ~i~-th member stays, or _ if they leave. Each index ~i~ should have at least one character _ next to it, and there should be exactly ~M~ character Ms in the string. If there exist multiple optimal scenarios, output any one of them.

Scoring

For each test case:

If the integer ~M~ you output is not maximal, your score will be ~0~ and you will receive a Wrong Answer verdict.

If the integer ~M~ you output is maximal but your configuration is invalid or missing, you will receive ~50~ points.

Otherwise, you will receive ~100~ points.

Your score for a subtask will be the minimum score over all test cases in the subtask multiplied by the weight of the subtask.

Your final score will be the sum of the scores of all the subtasks.

Sample Input

4

Sample Output

2
_MM_