To prepare a task for the CCPC Final, Little Cyan Fish is studying basic string theory. Today, Little Cyan Fish has learned the concept of the CCPC string. A string $s$ is called a CCPC string if and only if there exists a positive integer $t \ge 1$, such that $s=\text{c}^{2t}\text{pc}^t$. Here, $\text{c}^k$ represents the string consisting of the character `c` repeated $k$ times, and $\text{uv}$ denotes the string obtained by concatenating strings $\text{u}$ and $\text{v}$. For example, `ccpc`, `ccccpcc`, and `ccccccpccc` are CCPC strings, but `p`, `cpc`, `ccpcc`, `ccppc`, and `cccpc` are not. Now, Little Cyan Fish has a string $S$ consisting of `c`, `p`, and question marks (`?`). He wants to calculate the number of pairs of integers $(l, r)$ that satisfy the following conditions: - $1 \le l \le r \le |S|$ - for the string $T = S[l \cdots r]$, it is possible to replace the question marks (`?`) to `c` or `p`, so that the string is an CCPC string.

There are multiple test cases. The first line contains one integer $T$ $(1 \le T \le 10^5)$, representing the number of test cases. For each test case, the first line contains a single string $S$. The string $S$ consists only of the English letters `c`, `p`, and the question mark (`?`). It is guaranteed that the sum of $|S|$ over all test cases does not exceed $10^6$.

For each test case, output a single line consists a single integer, indicating the answer.

In the first example, all valid pairs of $(l, r)$ are as follows. | $l=$ | $r=$ | $S[l \cdots r]$ | Replaced String | | :--: | :--: | :-------------: | :-------------: | | $1$ | $4$ | `?cpc` | `ccpc` | In the second example, all valid pairs of $(l, r)$ are as follows. | $l=$ | $r=$ | $S[l \cdots r]$ | Replaced String | | :--: | :--: | :-------------: | :-------------: | | $1$ | $4$ | `ccp?` | `ccpc` | In the third example, all valid pairs of $(l, r)$ are as follows. | $l=$ | $r=$ | $S[l \cdots r]$ | Replaced String | | :--: | :--: | :-------------: | :-------------: | | $1$ | $4$ | `???c` | `ccpc` | | $3$ | $6$ | `?c??` | `ccpc` | | $4$ | $7$ | `c???` | `ccpc` | | $1$ | $7$ | `???c???` | `ccccpcc` | In the fourth example, all valid pairs of $(l, r)$ are as follows. | $l=$ | $r=$ | $S[l \cdots r]$ | Replaced String | | :--: | :--: | :-------------: | :-------------: | | $1$ | $4$ | `?c??` | `ccpc` | | $2$ | $5$ | `c???` | `ccpc` | | $3$ | $6$ | `???c` | `ccpc` | | $5$ | $8$ | `?cp?` | `ccpc` | | $3$ | $9$ | `???cp??` | `ccccpcc` | In the fifth example, all valid pairs of $(l, r)$ are as follows. | $l=$ | $r=$ | $S[l \cdots r]$ | Replaced String | | :--: | :--: | :-------------: | :-------------: | | $1$ | $4$ | `?c??` | `ccpc` | | $2$ | $5$ | `c???` | `ccpc` | | $3$ | $6$ | `????` | `ccpc` | | $4$ | $7$ | `????` | `ccpc` | | $5$ | $8$ | `???c` | `ccpc` | | $9$ | $12$ | `ccp?` | `ccpc` | | $12$ | $15$ | `????` | `ccpc` | | $1$ | $7$ | `?c?????` | `ccccpcc` | | $2$ | $8$ | `c?????c` | `ccccpcc` | | $3$ | $9$ | `?????cc` | `ccccpcc` | | $7$ | $13$ | `?cccp??` | `ccccpcc` | | $1$ | $10$ | `?c?????ccc` | `ccccccpccc` | | $5$ | $14$ | `???cccp???` | `ccccccpccc` | | $3$ | $15$ | `?????cccp????` | `ccccccccpcccc` |

第八届中国大学生程序设计竞赛总决赛