Hi, I don’t mean to entrude, but I’m a customer, and I need you to attend to my problems.

There is someone leaving messages around the neighbourhood. This is a clear violation of HOA statutes and guidelines, and he needs to be caught. Somehow, he’s been able to avoiding my security, meaning I have to decode his messages to look for clues. I’ve figured out how he encodes the messages, so maybe you can figure out a way to decode his messages.

For your understanding, I’ve taken the generous liberty (nobody wants to work these days) of making everything 0-indexed, so the 0th character of a string will refer to the leftmost character of the string, the 1st character refers to the second leftmost character of the string.

To encode a plain message (U) of length L into an encoded message (E) a secret key, K, is used, such that 1 < K < L, K is prime, and K does not divide L. A pointer, p, is initialised to index 0. The 0th character of E is set to the character at index p in U (0, since you are clearly mentally deficient) . Then, index p is incremented by K. Then, the 1st character of E is set to the character at the index p, (the Kth character of U, if you are following). When the value of p exceeds the length of the message, p wraps around by setting p to be p % L . Characters are recorded until the E has L characters.

In general, the ith character of E is the (i*K%L)th character of U.

Please decode a message I found, and give me the key, K, that was used to encode it.

Input format

I will give you two lines of input. The first line contains L.

The second line contains the encoded message, E. I have wrapped the message in square brackets to clearly mark the start and end of the message (Since you are probably incapable of parsing the whitespace correctly). Please remove them before decoding.

Output format

Decode the message and give me the key that was used to encode it.

Example

Input:

28
[C kymenptun?Ia  gas oar eora]

Output:

5

I encoded this test message with a key = 5, if you decode the message, you should find that the plain message is “Can I speak to your manager?”.

P.S, IF You do not solve this, then I WILL be speaking to your manager.

Thanks,

Carin von Karen, HOA president.