{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e \u003cspan\u003e\u003ca href\u003d\"http://uva.onlinejudge.org/external/115/11552.pdf\"\u003e\u003cimg alt\u003d\"Download as PDF\" height\u003d\"26\" src\u003d\"http://uva.onlinejudge.org/components/com_onlinejudge/images/button_pdf.png\" title\u003d\"Download as PDF\" width\u003d\"100\"\u003e\u003c/a\u003e\u003c/span\u003e\u003c/p\u003e \n\u003cdiv\u003e \n \u003cdiv\u003e\n 11552 Fewest Flops\n \u003c/div\u003e \n \u003cdiv\u003e\n A common way to uniquely encode a string is by replacing its consecutive repeating characters (or\n \u003c/div\u003e \n \u003cdiv\u003e\n “chunks”) by the number of times the character occurs followed by the character itself. For example,\n \u003c/div\u003e \n \u003cdiv\u003e\n the string “aabbbaabaaaa” may be encoded as “2a3b2a1b4a”. (Note for this problem even a single\n \u003c/div\u003e \n \u003cdiv\u003e\n character “b” is replaced by “1b”.)\n \u003c/div\u003e \n \u003cdiv\u003e\n Suppose we have a string S and a number k such that k divides the length of S. Let S1 be the\n \u003c/div\u003e \n \u003cdiv\u003e\n substring of S from 1 to k, S2 be the substring of S from k + 1 to 2k, and so on. We wish to rearrange\n \u003c/div\u003e \n \u003cdiv\u003e\n the characters of each block Si\n \u003c/div\u003e \n \u003cdiv\u003e\n independently so that the concatenation of those permutations S\n \u003c/div\u003e \n \u003cdiv\u003e\n ′ has\n \u003c/div\u003e \n \u003cdiv\u003e\n as few chunks of the same character as possible. Output the fewest number of chunks.\n \u003c/div\u003e \n \u003cdiv\u003e\n For example, let S be “uuvuwwuv” and k be 4. Then S1 is “uuvu” and has three chunks, but may\n \u003c/div\u003e \n \u003cdiv\u003e\n be rearranged to “uuuv” which has two chunks. Similarly, S2 may be rearranged to “vuww”. Then S\n \u003c/div\u003e \n \u003cdiv\u003e\n ′\n \u003c/div\u003e \n \u003cdiv\u003e\n ,\n \u003c/div\u003e \n \u003cdiv\u003e\n or S1S2, is “uuuvvuww” which is 4 chunks, indeed the minimum number of chunks.\n \u003c/div\u003e \n \u003cdiv\u003e\n Input\n \u003c/div\u003e \n \u003cdiv\u003e\n The input begins with a line containing t (1 ≤ t ≤ 100), the number of test cases. The following t lines\n \u003c/div\u003e \n \u003cdiv\u003e\n contain an integer k and a string S made of no more than 1000 lowercase English alphabet letters. It\n \u003c/div\u003e \n \u003cdiv\u003e\n is guaranteed that k will divide the length of S.\n \u003c/div\u003e \n \u003cdiv\u003e\n Output\n \u003c/div\u003e \n \u003cdiv\u003e\n For each test case, output a single line containing the minimum number of chunks after we rearrange\n \u003c/div\u003e \n \u003cdiv\u003e\n S as described above.\n \u003c/div\u003e \n \u003cdiv\u003e\n Sample Input\n \u003c/div\u003e \n \u003cdiv\u003e\n 2\n \u003c/div\u003e \n \u003cdiv\u003e\n 5 helloworld\n \u003c/div\u003e \n \u003cdiv\u003e\n 7 thefewestflops\n \u003c/div\u003e \n \u003cdiv\u003e\n Sample Output\n \u003c/div\u003e \n \u003cdiv\u003e\n 8\n \u003c/div\u003e \n \u003cdiv\u003e\n 10\n \u003c/div\u003e \n\u003c/div\u003e"}}]}