题目描述

给定一个由 $n$ 条指令组成的程序。初始时，单个变量 $x$ 被赋值为 $0$ 。随后，指令有两种类型：

• 将 $x$ 加 $1$；
• 将 $x$ 减 $1$。

给定 $m$ 个如下格式的查询：

• 查询 $l$ $r$ —— 如果忽略第 $l$ 条到第 $r$ 条（包含两端）之间的所有指令，按顺序执行其余指令，变量 $x$ 会被赋予多少个不同的值？

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 1000$）—— 测试用例的数量。

接下来是 $t$ 个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 2 \cdot 10^5$）—— 程序中指令的数量和查询的数量。

每个测试用例的第二行包含一个程序 —— 一个由 $n$ 个字符组成的字符串：每个字符要么是 + 要么是 -，分别表示加一和减一指令。

接下来 $m$ 行，每行包含两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq n$）—— 查询的描述。

所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。所有测试用例的 $m$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出 $m$ 个整数 —— 对于每个查询 $l$，$r$，输出忽略第 $l$ 条到第 $r$ 条（包含两端）之间的所有指令，按顺序执行其余指令时，变量 $x$ 被赋予的不同值的数量。

说明/提示

第一个测试用例中每个查询剩余的指令如下：

1. 空程序 —— $x$ 只等于 $0$；
2. - —— $x$ 的值为 $0$ 和 $-1$；
3. ---+ —— $x$ 的值为 $0$，$-1$，$-2$，$-3$，$-2$ —— 其中有 $4$ 个不同的值；
4. +--+--+ —— 不同的值为 $1$，$0$，$-1$，$-2$ 。

样例

2
8 4
-+--+--+
1 8
2 8
2 5
1 1
4 10
+-++
1 1
1 2
2 2
1 3
2 3
3 3
1 4
2 4
3 4
4 4

1
2
4
4
3
3
4
2
3
2
1
2
2
2