Count Good Prefixes

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
You are given an integer $n$ and a string $s$ consisting only of characters 'a' and 'b'. Consider a string $t = \underbrace{s + s + \dots + s}_{n\text{ times}}$, i.e. the string obtained by concatenating $n$ copies of $s$. Find the number of nonempty prefixes of $t$ in which the number of occurrences of 'a' is strictly greater than the number of occurrences of 'b'. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first and only line of each test case contains the string $s$ and the integer $n$, separated by a single space. ### Output For each test case, print a single line containing one integer — the number of valid prefixes. ### Constraints  $1 \le T \le 100$  $1 \le s \le 10^3$  $1 \le n \le 10^9$  each character of $s$ is either 'a' or 'b' ### Subtasks **Subtask #1 (30 points):** $1 \le n \le 10^3$ **Subtask #2 (70 points):** original constraints ### Sample Input3 aba 2 baa 3 bba 3### Sample Output
5 6 0### Explanation **Example case 1:** The string $t$ is "abaaba". It has five prefixes which contain more as than bs: "a", "aba", "abaa", "abaab" and "abaaba". **Example case 2:** The string $t$ is "baabaabaa". The strings "baa", "baaba", "baabaa", "baabaab", "baabaaba" and "baabaabaa" are the six valid prefixes. **Example case 3:** The string $t$ is "bbabbabba". There is no prefix of this string which consists of more as than bs. Therefore, the answer is zero.
Author:  admin2 
Editorial  https://discuss.codechef.com/problems/GOODPREF 
Tags  admin2, april18, logic, math, string 
Date Added:  2042018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 