{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003eRead problems statements in \u003ca target\u003d\"_blank\" \nhref\u003d\"https://www.codechef.com/download/translated/JAN18/mandarin/XYHUMOQ.pdf\"\u003eMandarin chinese\u003c/a\u003e and \u003ca target\u003d\"_blank\" \nhref\u003d\"https://www.codechef.com/download/translated/JAN18/vietnamese/XYHUMOQ.pdf\"\u003eVietnamese\u003c/a\u003e as well.\u003c/h3\u003e\n\n\n\u003cp\u003eLet\u0027s define a \u003ci\u003e10-string\u003c/i\u003e as a string that contains only characters \u00271\u0027 and \u00270\u0027, starts with \u00271\u0027 and ends with \u00270\u0027. For example, \u003cb\u003e\"10101010\"\u003c/b\u003e, \u003cb\u003e\"100\"\u003c/b\u003e or \u003cb\u003e\"1010\"\u003c/b\u003e are 10-strings, while \u003cb\u003e\"011\"\u003c/b\u003e, \u003cb\u003e\"11120\"\u003c/b\u003e or \u003cb\u003e\"10101\"\u003c/b\u003e are not.\u003c/p\u003e\n\n\u003cp\u003eA subsequence of any 10-string is called \u003ci\u003ehumongous\u003c/i\u003e if it is of the form \"1010...10\" (\"10\" concatenated an arbitrary number of times).\u003c/p\u003e\n\n\u003cp\u003eFor example, the 10-string \u003cb\u003e\"110\"\u003c/b\u003e contains exactly 2 humongous subsequences and \u003cb\u003e\"1010\"\u003c/b\u003e contains exactly 4 humongous subsequences (formed using indices \u003cb\u003e{1, 2}\u003c/b\u003e, \u003cb\u003e{3, 4}\u003c/b\u003e, \u003cb\u003e{1, 4}\u003c/b\u003e, \u003cb\u003e{1, 2, 3, 4}\u003c/b\u003e).\u003c/p\u003e\n\n\u003cp\u003eYou should process some really humongous queries. Each query is as follows:\n\u003cul\u003e\n\u003cli\u003eYou\u0027re given a 10-string \u003cb\u003eS\u003c/b\u003e and an integer \u003cb\u003eX\u003c/b\u003e.\u003c/li\u003e\n\u003cli\u003eYou should convert \u003cb\u003eS\u003c/b\u003e into another 10-string \u003cb\u003eU\u003c/b\u003e by flipping a number of characters (possibly zero; a flip means changing a \u00271\u0027 to \u00270\u0027 or \u00270\u0027 to \u00271\u0027) of \u003cb\u003eS\u003c/b\u003e.\u003c/li\u003e\n\u003cli\u003eThe string \u003cb\u003eU\u003c/b\u003e should contain exactly \u003cb\u003eX\u003c/b\u003e humongous subsequences.\u003c/li\u003e\n\u003cli\u003eThe answer to the query is the \u003cb\u003eminimum\u003c/b\u003e number of flips that need to be performed. If it\u0027s impossible to convert \u003cb\u003eS\u003c/b\u003e into a valid string \u003cb\u003eU\u003c/b\u003e, the answer doesn\u0027t exist.\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/p\u003e\n\n\u003cp\u003eNote that \u003cb\u003eU\u003c/b\u003e has to be a 10-string.\u003c/p\u003e\n\n\u003cp\u003eFor each query, compute the minimum possible number of flips or determine that there is no answer.\u003c/p\u003e\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cp\u003e\u003cul\u003e\n\u003cli\u003eThe first line of the input contains a single integer \u003cb\u003eT\u003c/b\u003e denoting the number of test cases. The description of \u003cb\u003eT\u003c/b\u003e test cases follows.\u003c/li\u003e\n\u003cli\u003eThe first line of each test case contains a single string \u003cb\u003eS\u003c/b\u003e.\u003c/li\u003e\n\u003cli\u003eThe second line contains a single integer \u003cb\u003eX\u003c/b\u003e.\u003c/li\u003e\n\u003c/ul\u003e\u003c/p\u003e\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003eFor each test case:\n\u003cul\u003e\n\u003cli\u003eIf there is no answer, print a single line containing one string \u003ctt\u003e\"NO\"\u003c/tt\u003e (without quotes).\u003c/li\u003e\n\u003cli\u003eIf an answer exists, print two lines.\u003c/li\u003e\n\u003cli\u003eThe first line should contains a single string \u003ctt\u003e\"YES\"\u003c/tt\u003e (without quotes).\u003c/li\u003e\n\u003cli\u003eThe second line should contain a single integer denoting the minimum necessary number of flips.\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/p\u003e\n\n\u003ch3\u003eConstraints\u003c/h3\u003e\n\u003cul\u003e\n\u003cli\u003e1 ≤ \u003cb\u003eT\u003c/b\u003e ≤ 10\u003c/li\u003e\n\u003cli\u003e2 ≤ \u003cb\u003e|S|\u003c/b\u003e ≤ 32\u003c/li\u003e\n\u003cli\u003e1 ≤ \u003cb\u003eX\u003c/b\u003e ≤ 10\u003csup\u003e6\u003c/sup\u003e\u003c/li\u003e\n\u003cli\u003e\u003cb\u003eS\u003c/b\u003e will be a 10-string\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003ch3\u003eSubtasks\u003c/h3\u003e\n\u003cp\u003e\u003cb\u003eSubtask #1 (15 points):\u003c/b\u003e\n\u003cul\u003e\n\u003cli\u003e\u003cb\u003e|S|\u003c/b\u003e ≤ 20\u003c/li\u003e\n\u003cli\u003e\u003cb\u003eX\u003c/b\u003e ≤ 10\u003csup\u003e3\u003c/sup\u003e\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eSubtask #2 (85 points):\u003c/b\u003e original constraints\u003c/p\u003e"}},{"title":"Sample 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n1110\n4\n110\n1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eYES\n1\nNO\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cp\u003e\u003cb\u003eExample case 1:\u003c/b\u003e We can convert the given 10-string into \u003cb\u003eU\u003c/b\u003e \u003d \"1010\" using only one flip; this string has exactly 4 humongous subsequences. This is the minimum possible number of flips.\u003c/p\u003e\n\u003cp\u003e\u003cb\u003eExample case 2:\u003c/b\u003e The only 10-strings we can obtain after any number of flips are \"100\" and \"110\". Each of them contains exactly 2 humongous subsequences, so there is no answer.\u003c/p\u003e"}}]}