{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eBaoBao is taking a walk in the interval $[0, n]$ on the number axis, but he is not free to move, as at every point $(i - 0.5)$ for all $i \\in [1, n]$, where $i$ is an integer, stands a traffic light of type $t_i$ ($t_i \\in \\{0, 1\\}$).\u003c/p\u003e\n\n\u003cp\u003eBaoBao decides to begin his walk from point $p$ and end his walk at point $q$ (both $p$ and $q$ are integers, and $p \u0026lt; q$). During each unit of time, the following events will happen \u003cb\u003ein order\u003c/b\u003e:\u003c/p\u003e\n\u003col\u003e\n \u003cli\u003e\u003cp\u003eLet\u0027s say BaoBao is currently at point $x$, he will then check the traffic light at point $(x + 0.5)$. If the traffic light is green, BaoBao will move to point $(x + 1)$; If the traffic light is red, BaoBao will remain at point $x$.\u003c/p\u003e\u003c/li\u003e\n \u003cli\u003e\u003cp\u003eAll the traffic lights change their colors. If a traffic light is currently red, it will change to green; If a traffic light is currently green, it will change to red.\u003c/p\u003e\u003c/li\u003e\n\u003c/ol\u003e\n\n\u003cp\u003eA traffic light of type 0 is initially red, and a traffic light of type 1 is initially green.\u003c/p\u003e\n\n\u003cp\u003eDenote $t(p, q)$ as the total units of time BaoBao needs to move from point $p$ to point $q$. For some reason, BaoBao wants you to help him calculate $\\sum_{p\u003d0}^{n-1}\\sum_{q\u003dp+1}^n t(p, q)$ where both $p$ and $q$ are integers. Can you help him?\u003c/p\u003e\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003eThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:\u003c/p\u003e\n\n\u003cp\u003eThe first and only line contains a string $s$ ($1 \\le |s| \\le 10^5$, $|s| \u003d n$, $s_i \\in \\{\\text{\u00270\u0027}, \\text{\u00271\u0027}\\}$ for all $1 \\le i \\le |s|$), indicating the types of the traffic lights. If $s_i \u003d \\text{\u00270\u0027}$, the traffic light at point $(i - 0.5)$ is of type 0 and is initially red; If $s_i \u003d \\text{\u00271\u0027}$, the traffic light at point $(i - 0.5)$ is of type 1 and is initially green.\u003c/p\u003e\n\n\u003cp\u003eIt\u0027s guaranteed that the sum of $|s|$ of all test cases will not exceed $10^6$.\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003eFor each test case output one line containing one integer, indicating the answer.\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\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\u003e3\n101\n011\n11010\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e12\n15\n43\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003ch4\u003eHint\u003c/h4\u003e\n\u003cp\u003eFor the first sample test case, it\u0027s easy to calculate that $t(0, 1) \u003d 1$, $t(0, 2) \u003d 2$, $t(0, 3) \u003d 3$, $t(1, 2) \u003d 2$, $t(1, 3) \u003d 3$ and $t(2, 3) \u003d 1$, so the answer is $1 + 2 + 3 + 2 + 3 + 1 \u003d 12$.\u003c/p\u003e\n\n\u003cp\u003eFor the second sample test case, it\u0027s easy to calculate that $t(0, 1) \u003d 2$, $t(0, 2) \u003d 3$, $t(0, 3) \u003d 5$, $t(1, 2) \u003d 1$, $t(1, 3) \u003d 3$ and $t(2, 3) \u003d 1$, so the answer is $2 + 3 + 5 + 1 + 3 + 1 \u003d 15$.\u003c/p\u003e\n"}}]}