{"raw_statement":[{"iden":"problem statement","content":"You are given a string $S$ of length $N$ consisting of lowercase English letters, and a positive integer $K$.\nDetermine whether there is a string $S'$ of length $K$ that satisfies the following conditions.\n\n*   The concatenation of $S$ and $S'$ in this order is a palindrome.\n*   The concatenation of $S'$ and $S$ in this order is a palindrome.\n\nYou have $T$ test cases to solve."},{"iden":"constraints","content":"*   $1 \\leq T \\leq 10^5$\n*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq K \\leq 10^{18}$\n*   $S$ is a string of length $N$ consisting of lowercase English letters.\n*   All numbers in the input are integers.\n*   In each input file, the sum of $N$ over the test cases is at most $2 \\times 10^5$."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\vdots$\n$\\mathrm{case}_T$\n\nEach case is in the following format:\n\n$N$ $K$\n$S$"},{"iden":"sample input 1","content":"2\n6 2\nabbaab\n5 3\nabcbb"},{"iden":"sample output 1","content":"Yes\nNo\n\nFor the first test case, if we let $S' = {}$`ba`, for instance, the concatenation of $S$ and $S'$ in this order will be `abbaabba`, which is a palindrome. Here, the concatenation of $S'$ and $S$ in this order is `baabbaab`, which is also a palindrome. Thus, $S' = {}$`ba` satisfies the condition, so the answer is `Yes`.\nFor the second test case, we can prove that no string satisfies the conditions."},{"iden":"sample input 2","content":"3\n12 400378271514996652\nnjvhhvjnnjvh\n10 884633988115575508\nrrhiyvrrur\n36 71630165869626180\nvsxmxajrrduhhudrrjaxmxsvvsxmxajrrduh"},{"iden":"sample output 2","content":"Yes\nNo\nYes"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}