{"raw_statement":[{"iden":"problem statement","content":"As a token of his gratitude, Takahashi has decided to give Snuke a level-$K$ palindrome. A level-$L$ palindrome, where $L$ is a non-negative integer, is defined as follows:\n\n*   Let $\\mathrm{rev}(s)$ denote the reversal of a string $s$.\n*   A string $s$ is said to be a palindrome when $s = \\mathrm{rev}(s)$.\n*   The empty string and a string that is not a palindrome are level-$0$ palindromes.\n*   For any **non-empty** level-$(L-1)$ palindrome $t$, the concatenation of $t, \\mathrm{rev}(t)$ in this order is a level-$L$ palindrome.\n*   For any level-$(L-1)$ palindrome $t$ and any character $c$, the concatenation of $t, c, \\mathrm{rev}(t)$ in this order is a level-$L$ palindrome.\n\nNow, Takahashi has a string $S$. Determine whether it is possible to make $S$ an exactly level-$K$ palindrome by doing the following action zero or more times: choose a character in $S$ and change it to another lowercase English letter. If it is possible, find the minimum number of changes needed to make $S$ a level-$K$ palindrome."},{"iden":"constraints","content":"*   $K$ is an integer.\n*   $0 ≤ K ≤ 5 \\times 10^5$\n*   $S$ consists of lowercase English letters.\n*   $1 ≤ |S| ≤ 5 \\times 10^5$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$K$\n$S$"},{"iden":"sample input 1","content":"4\naabaaaabaa"},{"iden":"sample output 1","content":"0\n\nWe can find the level of `aabaaaabaa` as follows:\n\n*   the empty string is a level-$0$ palindrome;\n*   `a` is a concatenation of (empty string), `a`, (empty string) in this order, so it is a level-$1$ palindrome;\n*   `aa` is a concatenation of `a`, `a` in this order, so it is a level-$2$ palindrome;\n*   `aabaa` is a concatenation of `aa`, `b`, `aa` in this order, so it is a level-$3$ palindrome;\n*   `aabaaaabaa` is a concatenation of `aabaa`, `aabaa` in this order, so it is a level-$4$ palindrome.\n\nThus, `aabaaaabaa` is already a level-$4$ palindrome and needs no changes."},{"iden":"sample input 2","content":"2\naabaaaabaa"},{"iden":"sample output 2","content":"4\n\nWe can, for example, change `aabaaaabaa` to `acbcaacbca` to get a level-$2$ palindrome.\nNote that `aabaaaabaa` is not a level-$2$ palindrome."},{"iden":"sample input 3","content":"3\naabaaaabaa"},{"iden":"sample output 3","content":"impossible"},{"iden":"sample input 4","content":"5\naabaaaabaa"},{"iden":"sample output 4","content":"impossible"},{"iden":"sample input 5","content":"2\nacaabcbababaaac"},{"iden":"sample output 5","content":"6"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}