{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003e Read problems statements in \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/LTIME32/mandarin/EXPALIN.pdf\"\u003eMandarin Chinese \u003c/a\u003e, \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/LTIME32/russian/EXPALIN.pdf\"\u003eRussian\u003c/a\u003e and \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/LTIME32/vietnamese/EXPALIN.pdf\"\u003eVietnamese\u003c/a\u003e as well.\u003c/h3\u003e\r\n\r\n\r\n\u003cp\u003e\r\nYou are given a binary string \u003cb\u003eS\u003c/b\u003e of \u003cb\u003eN\u003c/b\u003e bits. The bits in the string are indexed starting from 1. \u003cb\u003eS[i]\u003c/b\u003e denotes the \u003cb\u003ei\u003c/b\u003e\u003csup\u003eth\u003c/sup\u003e bit of \u003cb\u003eS\u003c/b\u003e.\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\nLet\u0027s say that a sequence \u003cb\u003ei\u003csub\u003e1\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003ei\u003csub\u003e2\u003c/sub\u003e\u003c/b\u003e, …, \u003cb\u003ei\u003csub\u003eK\u003c/sub\u003e\u003c/b\u003e(1 ≤ \u003cb\u003eK\u003c/b\u003e; 1 ≤ \u003cb\u003ei\u003csub\u003e1\u003c/sub\u003e\u003c/b\u003e \u003c \u003cb\u003ei\u003csub\u003e2\u003c/sub\u003e\u003c/b\u003e \u003c … \u003c \u003cb\u003ei\u003csub\u003eK\u003c/sub\u003e\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e) \u003ci\u003eproduces\u003c/i\u003e a palindrome when applied to \u003cb\u003eS\u003c/b\u003e, if the string \u003cb\u003eS[i\u003csub\u003e1\u003c/sub\u003e]\u003c/b\u003e \u003cb\u003eS[i\u003csub\u003e2\u003c/sub\u003e]\u003c/b\u003e … \u003cb\u003eS[i\u003csub\u003ek\u003c/sub\u003e]\u003c/b\u003e is a palindrome (that is, reads the same backward or forward).\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e \r\nIn addition, a sequence \u003cb\u003ei\u003csub\u003e1\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003ei\u003csub\u003e2\u003c/sub\u003e\u003c/b\u003e, …, \u003cb\u003ei\u003csub\u003eK\u003c/sub\u003e\u003c/b\u003e(1 ≤ \u003cb\u003eK\u003c/b\u003e; 1 ≤ \u003cb\u003ei\u003csub\u003e1\u003c/sub\u003e\u003c/b\u003e \u003c \u003cb\u003ei\u003csub\u003e2\u003c/sub\u003e\u003c/b\u003e \u003c … \u003c \u003cb\u003ei\u003csub\u003eK\u003c/sub\u003e\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e) is said to be \u003ci\u003eexponential\u003c/i\u003e, if \u003cb\u003ei\u003csub\u003ej + 1\u003c/sub\u003e \u003d p * i\u003csub\u003ej\u003c/sub\u003e\u003c/b\u003e for each integer \u003cb\u003e1 ≤ j \u003c K\u003c/b\u003e and for some integer \u003cb\u003ep \u003e 1\u003c/b\u003e. Note, that a sequence of one element is always exponential.\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003eYour task is to count the number of exponential sequences that produce a palindrome when applied to \u003cb\u003eS\u003c/b\u003e.\u003c/p\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe first line of input contains an integer \u003cb\u003eT\u003c/b\u003e denoting the number of test cases. The description of \u003cb\u003eT\u003c/b\u003e test cases follows.\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\nThe only line of description for each test case contains a binary string \u003cb\u003eS\u003c/b\u003e of \u003cb\u003eN\u003c/b\u003e bits.\r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003e\r\nFor each test case, output a single line containing the number of exponential sequences that produce a palindrome.\r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e1 ≤ \u003cb\u003eT\u003c/b\u003e ≤ 10\u003c/li\u003e\r\n\u003cli\u003eSubtask 1(20 points): 1 ≤ \u003cb\u003eN\u003c/b\u003e ≤ 20\u003c/li\u003e\r\n\u003cli\u003eSubtask 2(30 points): 1 ≤ \u003cb\u003eN\u003c/b\u003e ≤ 1000\u003c/li\u003e\r\n\u003cli\u003eSubtask 3(50 points): 1 ≤ \u003cb\u003eN\u003c/b\u003e ≤ 5 × 10\u003csup\u003e5\u003c/sup\u003e\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\n\u003ch3\u003eNote\u003c/h3\u003e\r\n\u003cp\u003e\r\nThe first test of the first subtask is the example test. It\u0027s made for you to make sure that your solution produces the same verdict both on your machine and our server.\r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003eTime Limits\u003c/h3\u003e\r\n\u003cp\u003e\r\nTime limit for the first and the second subtasks is 3s. Time limit for the third subtask is 6s.\r\n\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\r\n11010\r\n101001011\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e9\r\n18\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}