Scientists studying Pandora have discovered that the entire planet is one large living organism connected to a collective consciousness called Eywa. All living beings on Pandora can establish a connection with Eywa and communicate with it.

To create a new prototype of Avatars, scientists decided to focus on making the Avatars closer to Eywa and enable them to control phenomena on the planet with its help. To achieve this, they are editing the genetic code of the current generation of Avatars.

There are a total of $$$n$$$ avatars in the current generation ($$$n$$$ is even), where the $$$i$$$-th avatar has a genetic code fragment responsible for the connection with Eywa. This fragment is obtained by cyclically shifting a string $$$s$$$ of length $$$n$$$ by $$$i$$$ positions, which means it contains the characters $$$s_i, s_{i+1}, \ldots, s_n, s_1, s_2, \ldots, s_{i-1}$$$.

New Avatars are planned to be obtained through recombination: the genetic codes of two Avatars from the first generation are taken and written down character by character in sequence. The first character is taken from the first individual, the second from the second individual, the third from the first individual, and so on. Thus, when recombining the $$$i$$$-th and $$$j$$$-th Avatars, the resulting string is $$$s_i, s_{(j+1) \bmod n}, s_{(i+2) \bmod n}, s_{(j+3) \bmod n}, \ldots, s_{(i+n-2) \bmod n}, s_{(j+n-1) \bmod n}$$$.

Scientists are interested in knowing how many pairs of individuals from the first generation exist, such that their recombination results in a new genetic code that is not represented in the first generation and is responsible for the ability to connect with Eywa. If there are two pairs of individuals $$$(i_1, j_1)$$$ and $$$(i_2, j_2)$$$ that produce the same new genetic code, both of them should be counted in the answer.

Points are awarded for each subtask only if all tests of that subtask and the required subtasks are passed.