You are given a program that consists of $$$n$$$ instructions. Initially, a single variable $$$x$$$ is assigned to $$$1$$$.
Afterwards, the instructions are of two types:
You are given $$$m$$$ queries of the following format:
The first line contains a single integer $$$t$$$ $$$(1\leq t \leq 1000)- $$$the number of test cases.
The first line of each test case contains two integers $$$n$$$ and $$$q$$$ $$$(1\leq n,q \leq 10^{6})- $$$the number of instructions in the program and the number of queries.
The second line of each testcase contains a program $$$-$$$ a string of $$$n$$$ characters: each character is either '$$$*$$$' or '$$$/$$$' $$$-$$$ multiply and divide instruction, respectively.
Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ $$$(1\leq l \leq r \leq n)-$$$ the description of the query.
The sum of $$$n$$$ over all test cases doesn't exceed $$$10^{6}$$$. The sum of $$$q$$$ over all test cases doesn't exceed $$$10^{6}$$$.
For each test case, print $$$q$$$ integers $$$-$$$ for each query $$$l$$$,$$$r$$$, print the number of distinct values variable $$$x$$$ is assigned to if all the instructions between the $$$l_{th}$$$ one and the $$$r_{th}$$$ one inclusive are executed without changing the order and $$$x$$$ always starts with $$$1$$$.
212 5*/**///*/*//1 42 76 101 124 85 3*//**1 32 52 4
3 2 2 4 3 3 2 2
Name |
---|