使用 proxy-tools 脚本简化 SSH 远程转发

SSH 远程端口转发 (ssh -R) 是一个非常有用的功能，它允许我们将本地机器上的端口暴露给远程服务器访问，从而让远程服务器通过本地代理访问网络。

例如，我们可以使用以下命令将本地的 3128 端口（假设运行着 Squid 代理）转发到远程服务器 user@server_ip 的 3129 端口：

1

ssh -R 3129:localhost:3128 user@server_ip

之后，在远程服务器上访问 127.0.0.1:3129 就相当于访问发起连接的本地机器的 localhost:3128。

然而，直接使用 ssh -R 命令存在一些不便之处：

1. 连接脆弱：网络波动或长时间无活动可能导致 SSH 连接中断，转发随之失效。
2. 手动维护：需要手动保持 SSH 进程在后台运行（例如使用 nohup, screen, tmux），并在中断后手动重连。
3. 不易管理：启动、停止和检查状态不够直观。

为了解决连接稳定性问题，autossh 工具应运而生。它能够监控 SSH 连接，并在断开时自动尝试重新建立。

但这仍然需要用户自行管理 autossh 进程。

proxy-tools：一个管理脚本

为了进一步简化这个过程，proxy-tools 脚本被创建出来。它结合了 autossh 的连接保持能力和 systemd 的服务管理能力，提供了一套更便捷的管理方案。

主要目标：

• 通过 systemd 服务实现 autossh 隧道的后台稳定运行和自动重启。
• 提供简单的命令行接口 (proxyon, proxyoff, proxystatus) 来控制隧道的启动、停止和状态查询。
• 通过交互式脚本简化安装和卸载过程。

工作原理简介

proxy-tools 的核心是利用 systemd 服务来管理 autossh 进程。

1. 安装：脚本会创建一个 systemd 服务模板文件 (autossh-proxy@.service)，该模板定义了如何启动一个 autossh 远程转发实例。同时，它会生成三个辅助脚本 (proxyon.sh, proxyoff.sh, proxystatus.sh) 到用户目录下的 ~/proxy-tools。
2. **启动 (proxyon)**：当用户执行 proxyon user@server_ip 时，脚本会调用 systemctl 来启动一个基于模板的服务实例（如 autossh-proxy@user@server_ip.service）。systemd 随后根据模板配置，以后台服务的形式运行 autossh，建立并维护到指定服务器的 -R 转发隧道。
3. **停止 (proxyoff)**：该命令会找到当前活动的服务实例，并使用 systemctl 将其停止并禁用。
4. **状态 (proxystatus)**：该命令会查询当前活动服务实例的状态信息。

使用准备

在安装和使用 proxy-tools 之前，请确保满足以下条件：

• 系统环境：运行脚本的本地机器需要是使用 systemd 的 Linux 系统。
• 软件依赖：已安装 autossh (例如 sudo apt install autossh)。
• 权限：拥有 sudo 权限，因为需要管理 systemd 服务。
• SSH 认证：强烈建议配置好本地机器到目标服务器 (user@server_ip) 的 SSH 密钥免密登录。否则 autossh 可能无法在后台成功连接。
• 本地服务：确保你想要转发的本地端口（默认为 3128）有服务正在监听。

安装步骤

1. 获取 manage-proxy-tools.sh 脚本（例如通过下载或 Git clone）。

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376

   #!/bin/bash # Exit immediately if a command exits with a non-zero status. set -e # --- Configuration --- INSTALL_DIR="$HOME/proxy-tools" SERVICE_NAME_BASE="autossh-proxy" # Base name for systemd service template SYSTEMD_SERVICE_FILE="/etc/systemd/system/${SERVICE_NAME_BASE}@.service" HELPER_SCRIPTS=("proxyon.sh" "proxyoff.sh" "proxystatus.sh") TARGET_INFO_FILE="${INSTALL_DIR}/target.info" # Stores the current user@host # Ports (as per your request) LOCAL_SQUID_PORT="3128" REMOTE_FORWARD_PORT="3129" AUTOSSH_MONITOR_PORT="20000" # Monitor port for autossh (-M) # Alias configuration ALIAS_ON="alias proxyon='${INSTALL_DIR}/proxyon.sh'" ALIAS_OFF="alias proxyoff='${INSTALL_DIR}/proxyoff.sh'" ALIAS_STATUS="alias proxystatus='${INSTALL_DIR}/proxystatus.sh'" ALIAS_COMMENT="# Added by proxy-tools" # --- Helper Functions --- check_dependencies() { echo "检查依赖..." if ! command -v autossh &> /dev/null; then echo "错误: 'autossh' 未安装。请先安装它 (例如: sudo apt install autossh)" exit 1 fi if ! command -v systemctl &> /dev/null; then echo "错误: 'systemd' (systemctl) 未找到。此脚本需要 systemd。" exit 1 fi if [ "$(id -u)" -eq 0 ]; then echo "错误：请不要直接使用 root 用户运行此安装脚本。" echo "脚本会在需要时使用 'sudo' 请求权限。" exit 1 fi echo "依赖检查通过。" } check_sudo() { if ! sudo -v; then echo "错误：无法获取 sudo 权限。请确保你有 sudo 权限并且可以免密或者输入密码。" exit 1 fi } add_aliases() { local shell_rc echo "尝试添加别名到 .bashrc 和 .zshrc..." for shell_rc in "$HOME/.bashrc" "$HOME/.zshrc"; do if [ -f "$shell_rc" ]; then # Check if alias already exists if ! grep -qF "$ALIAS_COMMENT" "$shell_rc"; then echo "添加别名到 $shell_rc" echo "" >> "$shell_rc" echo "$ALIAS_COMMENT" >> "$shell_rc" echo "$ALIAS_ON" >> "$shell_rc" echo "$ALIAS_OFF" >> "$shell_rc" echo "$ALIAS_STATUS" >> "$shell_rc" else echo "别名似乎已存在于 $shell_rc" fi fi done echo "完成。请运行 'source ~/.bashrc' 或 'source ~/.zshrc' 或重新打开终端以使别名生效。" } remove_aliases() { local shell_rc echo "尝试从 .bashrc 和 .zshrc 移除别名..." for shell_rc in "$HOME/.bashrc" "$HOME/.zshrc"; do if [ -f "$shell_rc" ]; then # 检查注释标记是否存在 if grep -qF "$ALIAS_COMMENT" "$shell_rc"; then echo "从 $shell_rc 移除别名..." # 使用 # 作为 sed 的分隔符，避免与路径中的 / 冲突 # 同时移除注释标记和其后的别名行 sed -i -e "#^${ALIAS_COMMENT}$#d" \ -e "#^${ALIAS_ON}$#d" \ -e "#^${ALIAS_OFF}$#d" \ -e "#^${ALIAS_STATUS}$#d" "$shell_rc" else # 如果找不到注释标记，也尝试直接删除别名（以防万一） echo "在 $shell_rc 中未找到注释标记，尝试直接移除别名..." sed -i -e "#^${ALIAS_ON}$#d" \ -e "#^${ALIAS_OFF}$#d" \ -e "#^${ALIAS_STATUS}$#d" "$shell_rc" fi fi done echo "完成。" } # --- Installation Function --- install_proxy_tools() { echo "开始安装 proxy-tools..." check_dependencies check_sudo # Create installation directory mkdir -p "$INSTALL_DIR" echo "安装目录: $INSTALL_DIR" # --- Create proxyon.sh --- cat << EOF > "${INSTALL_DIR}/proxyon.sh" #!/bin/bash set -e SERVICE_NAME_BASE="${SERVICE_NAME_BASE}" TARGET_INFO_FILE="${TARGET_INFO_FILE}" if [ -z "\$1" ]; then echo "用法: \$0 <user@server_ip>" exit 1 fi TARGET="\$1" SERVICE_INSTANCE="\${SERVICE_NAME_BASE}@\${TARGET}.service" echo "检查当前是否有活动的代理服务..." if [ -f "\$TARGET_INFO_FILE" ]; then CURRENT_TARGET=\$(cat "\$TARGET_INFO_FILE") CURRENT_SERVICE_INSTANCE="\${SERVICE_NAME_BASE}@\${CURRENT_TARGET}.service" # Check if the service file exists and is active/enabled if systemctl --quiet is-active "\$CURRENT_SERVICE_INSTANCE" || systemctl --quiet is-enabled "\$CURRENT_SERVICE_INSTANCE"; then if [ "\$CURRENT_TARGET" != "\$TARGET" ]; then echo "错误：似乎已有另一个代理实例 (\$CURRENT_TARGET) 正在运行或已启用。" echo "请先使用 'proxyoff' 停止当前服务，然后再启动新的服务。" exit 1 else echo "代理服务 (\$TARGET) 似乎已在运行或已启用。" echo "尝试重启服务..." fi fi fi echo "正在启动/重启代理服务: \$SERVICE_INSTANCE ..." # Use --now to enable and start immediately sudo systemctl enable --now "\$SERVICE_INSTANCE" if sudo systemctl is-active --quiet "\$SERVICE_INSTANCE"; then echo "\$TARGET" > "\$TARGET_INFO_FILE" # Store the target on success echo "代理服务已成功启动并启用。" echo "远程服务器端口 ${REMOTE_FORWARD_PORT} 已转发到本地 localhost:${LOCAL_SQUID_PORT}" echo "请在服务器上配置代理: export http_proxy=\"http://127.0.0.1:${REMOTE_FORWARD_PORT}\" https_proxy=\"http://127.0.0.1:${REMOTE_FORWARD_PORT}\"" else echo "错误：启动服务失败。请检查日志：sudo journalctl -u \$SERVICE_INSTANCE -n 50" # Clean up target file if start failed if [ -f "\$TARGET_INFO_FILE" ] && [ "\$(cat "\$TARGET_INFO_FILE")" == "\$TARGET" ]; then rm -f "\$TARGET_INFO_FILE" fi exit 1 fi EOF # --- Create proxyoff.sh --- cat << EOF > "${INSTALL_DIR}/proxyoff.sh" #!/bin/bash set -e SERVICE_NAME_BASE="${SERVICE_NAME_BASE}" TARGET_INFO_FILE="${TARGET_INFO_FILE}" if [ ! -f "\$TARGET_INFO_FILE" ]; then echo "没有找到活动的代理目标信息 (\$TARGET_INFO_FILE)。" echo "尝试查找并停止任何 autossh-proxy@* 服务..." ACTIVE_SERVICES=\$(systemctl list-units --type=service --state=active "${SERVICE_NAME_BASE}@*.service" --no-legend | awk '{print \$1}') if [ -z "\$ACTIVE_SERVICES" ]; then echo "未找到活动的 ${SERVICE_NAME_BASE}@* 服务。" exit 0 else echo "警告：找到以下活动服务，将尝试全部停止：" echo "\$ACTIVE_SERVICES" for service in \$ACTIVE_SERVICES; do echo "正在停止 \$service..." sudo systemctl stop "\$service" echo "正在禁用 \$service (防止重启后自启)..." sudo systemctl disable "\$service" done echo "所有找到的 ${SERVICE_NAME_BASE}@* 服务已停止并禁用。" exit 0 fi fi TARGET=\$(cat "\$TARGET_INFO_FILE") SERVICE_INSTANCE="\${SERVICE_NAME_BASE}@\${TARGET}.service" echo "正在停止代理服务: \$SERVICE_INSTANCE ..." sudo systemctl stop "\$SERVICE_INSTANCE" echo "正在禁用代理服务 (防止重启后自启)..." sudo systemctl disable "\$SERVICE_INSTANCE" # Clean up target info file after stopping rm -f "\$TARGET_INFO_FILE" echo "代理服务已停止并禁用。" EOF # --- Create proxystatus.sh --- cat << EOF > "${INSTALL_DIR}/proxystatus.sh" #!/bin/bash SERVICE_NAME_BASE="${SERVICE_NAME_BASE}" TARGET_INFO_FILE="${TARGET_INFO_FILE}" echo "检查代理服务状态..." if [ -f "\$TARGET_INFO_FILE" ]; then TARGET=\$(cat "\$TARGET_INFO_FILE") SERVICE_INSTANCE="\${SERVICE_NAME_BASE}@\${TARGET}.service" echo "当前配置的目标: \$TARGET" echo "对应的服务单元: \$SERVICE_INSTANCE" sudo systemctl status "\$SERVICE_INSTANCE" --no-pager else echo "未找到当前活动的代理目标信息 (\$TARGET_INFO_FILE)。" echo "你可以尝试手动检查特定服务: sudo systemctl status ${SERVICE_NAME_BASE}@<user@server_ip>.service" echo "或者检查所有可能的实例: systemctl list-units --type=service '${SERVICE_NAME_BASE}@*.service'" fi EOF # Make helper scripts executable chmod +x "${INSTALL_DIR}/proxyon.sh" "${INSTALL_DIR}/proxyoff.sh" "${INSTALL_DIR}/proxystatus.sh" echo "辅助脚本已创建并设为可执行。" # --- Create systemd service file --- # Get the username who invoked sudo, or the current user if not using sudo (fallback) INSTALL_USER=${SUDO_USER:-$(whoami)} echo "为用户 '$INSTALL_USER' 创建 systemd 服务文件..." # Use a heredoc with sudo tee to write the systemd file sudo tee "$SYSTEMD_SERVICE_FILE" > /dev/null << EOF [Unit] Description=Autossh tunnel for proxy (%I) After=network.target # StartLimitIntervalSec=0 # Removed for potentially better restart behavior [Service] User=${INSTALL_USER} Environment="AUTOSSH_GATETIME=0" Environment="AUTOSSH_POLL=60" # Check connection every 60 seconds # -M: Monitor port, -N: No remote command, -T: No TTY # -o options for robustness: keepalive, exit on failure ExecStart=/usr/bin/autossh -M ${AUTOSSH_MONITOR_PORT} -NT \ -o "ServerAliveInterval=60" \ -o "ServerAliveCountMax=3" \ -o "ExitOnForwardFailure=yes" \ -o "ConnectTimeout=10" \ -o "StrictHostKeyChecking=no" \ -R ${REMOTE_FORWARD_PORT}:localhost:${LOCAL_SQUID_PORT} %i RestartSec=5 Restart=always # Restart the service if it fails [Install] WantedBy=multi-user.target EOF echo "Systemd 服务文件已创建: $SYSTEMD_SERVICE_FILE" # Reload systemd daemon echo "重新加载 systemd 配置..." sudo systemctl daemon-reload # Ask about aliases read -p "是否要将 proxyon, proxyoff, proxystatus 添加到 shell 别名? (y/N): " add_alias_confirm if [[ "$add_alias_confirm" =~ ^[Yy]$ ]]; then add_aliases else echo "跳过添加别名。你可以手动运行脚本:" echo " ${INSTALL_DIR}/proxyon.sh <user@server_ip>" echo " ${INSTALL_DIR}/proxyoff.sh" echo " ${INSTALL_DIR}/proxystatus.sh" fi echo "" echo "--------------------------------------" echo "✅ proxy-tools 安装完成!" echo "--------------------------------------" echo "使用方法:" echo " proxyon user@server_ip # 启动代理 (如果添加了别名)" echo " proxyoff # 停止代理 (如果添加了别名)" echo " proxystatus # 查看状态 (如果添加了别名)" echo "" echo "或者直接运行脚本:" echo " ${INSTALL_DIR}/proxyon.sh user@server_ip" echo " ${INSTALL_DIR}/proxyoff.sh" echo " ${INSTALL_DIR}/proxystatus.sh" echo "" echo "重要提示: 确保你的 SSH 密钥已配置好，可以免密登录到 user@server_ip。" echo " 否则 autossh 可能无法在后台成功连接。" echo "首次连接时，autossh 可能需要手动确认主机密钥。" echo "你可能需要手动运行一次 ssh user@server_ip 来添加主机密钥。" } # --- Uninstallation Function --- uninstall_proxy_tools() { echo "开始卸载 proxy-tools..." check_sudo # Stop and disable any running service instance echo "尝试停止并禁用所有相关的 systemd 服务..." # Find active/enabled instances first INSTANCES=$(systemctl list-units --type=service --state=active,enabled --no-legend "${SERVICE_NAME_BASE}@*.service" | awk '{print $1}') if [ -n "$INSTANCES" ]; then for instance in $INSTANCES; do echo "停止服务 $instance ..." sudo systemctl stop "$instance" || echo "停止 $instance 失败 (可能已停止)" echo "禁用服务 $instance ..." sudo systemctl disable "$instance" || echo "禁用 $instance 失败 (可能已禁用)" done else echo "未找到活动的或已启用的 ${SERVICE_NAME_BASE}@* 服务实例。" fi # Remove the systemd service file if [ -f "$SYSTEMD_SERVICE_FILE" ]; then echo "移除 systemd 服务文件: $SYSTEMD_SERVICE_FILE" sudo rm -f "$SYSTEMD_SERVICE_FILE" echo "重新加载 systemd 配置..." sudo systemctl daemon-reload else echo "Systemd 服务文件未找到，跳过移除。" fi # Remove aliases remove_aliases # Remove the installation directory if [ -d "$INSTALL_DIR" ]; then echo "移除安装目录: $INSTALL_DIR" rm -rf "$INSTALL_DIR" else echo "安装目录未找到，跳过移除。" fi echo "" echo "--------------------------------------" echo "🗑️ proxy-tools 卸载完成。" echo "--------------------------------------" echo "你可能需要重新启动你的 shell 或运行 'source ~/.bashrc' / 'source ~/.zshrc' 来完全移除别名。" } # --- Main Menu --- echo "==============================" echo " Proxy Tools 管理脚本" echo "==============================" echo "请选择操作:" echo " 1) 安装 proxy-tools" echo " 2) 卸载 proxy-tools" echo " 3) 退出" echo "------------------------------" read -p "输入选项 [1-3]: " choice case "$choice" in 1) install_proxy_tools ;; 2) uninstall_proxy_tools ;; 3) echo "退出。" exit 0 ;; *) echo "无效选项。" exit 1 ;; esac exit 0

2. 赋予执行权限：

   1	chmod +x manage-proxy-tools.sh

3. 运行安装脚本（请勿直接使用 sudo 运行）：

   1	./manage-proxy-tools.sh

4. 在菜单中选择 1) 安装 proxy-tools。脚本将检查依赖、创建目录和文件、设置 systemd 服务。

5. 脚本会询问是否添加别名到 ~/.bashrc 或 ~/.zshrc。选择 y 可以方便后续使用。

6. 如果添加了别名，需要重新加载 shell 配置或新开一个终端窗口：

   1	source ~/.bashrc # 或 source ~/.zshrc

使用方法

• 启动转发隧道：

  1 2 3 4 5

  # 如果设置了别名 proxyon <user@server_ip> # 或者直接运行脚本 ~/proxy-tools/proxyon.sh <user@server_ip>

  成功后，远程服务器 <server_ip> 上的 127.0.0.1:3129 (默认) 端口将连接到你本地机器的 localhost:3128 (默认) 端口。

• 在远程服务器上使用转发的端口：
  登录到远程服务器 (<server_ip>)，然后配置需要使用此隧道的应用程序。例如，若要将该隧道用作 HTTP/HTTPS 代理：

  1 2 3 4 5

  export http_proxy="http://127.0.0.1:3129" export https_proxy="http://127.0.0.1:3129" # 测试代理是否工作 wget www.google.com

• 停止转发隧道：

  1 2 3 4 5

  # 如果设置了别名 proxyoff # 或者直接运行脚本 ~/proxy-tools/proxyoff.sh

  该命令会停止当前活动的 autossh 服务实例。

• 检查隧道状态：

  1 2 3 4 5

  # 如果设置了别名 proxystatus # 或者直接运行脚本 ~/proxy-tools/proxystatus.sh

  该命令会显示当前活动服务实例的 systemd 状态信息。

配置选项

脚本默认使用以下配置：

• 本地监听端口 (LOCAL_SQUID_PORT): 3128
• 远程转发端口 (REMOTE_FORWARD_PORT): 3129 (在远程服务器上监听 127.0.0.1)
• autossh 监控端口 (AUTOSSH_MONITOR_PORT): 20000
• 安装目录: ~/proxy-tools

如需修改这些默认值，可以直接编辑 manage-proxy-tools.sh 脚本顶部的配置变量，然后重新运行安装程序 (选择 1) 以应用更改。

卸载方法

如果不再需要 proxy-tools，可以运行管理脚本进行清理：

1

./manage-proxy-tools.sh

选择 2) 卸载 proxy-tools。脚本会自动停止相关服务、删除 systemd 配置文件、移除 ~/proxy-tools 目录，并尝试清理添加的 shell 别名。

总结

proxy-tools 通过结合 autossh 和 systemd，为管理 SSH 远程转发隧道提供了一套相对简单和可靠的方案。它通过封装底层命令和利用系统服务管理，降低了使用门槛，提高了隧道的稳定性。对于需要频繁或长期使用 SSH 远程转发的用户来说，这可以是一个方便的管理工具。

注意事项

• 本地服务安全：转发本地端口意味着远程服务器可以访问该端口。确保本地服务（如 Squid）配置了适当的访问控制，防止未授权访问。脚本示例中提到的 Squid 配置 http_access allow all 通常是不安全的，应根据实际需要限制来源 IP。
• SSH 主机密钥：systemd 服务配置中可能包含 StrictHostKeyChecking=no 选项，以避免因目标主机密钥未知导致 autossh 启动失败。了解此选项的安全含义（连接时不会验证远程主机的身份）。在安全要求高的场景下，建议首次手动连接目标服务器以接受其主机密钥，然后考虑从服务配置中移除此选项。

CF1944D - Non-Palindromic Substring

题意：称一个字符串为$k$-good字符串，当该字符串至少有一个长度为$k$的子串不是回文串。给定一个字符串，询问$[l, r]$子串的$\sum{k}$

通过模拟可以发现对于一个字符串：

1. 不是回文串，则$k$可以取$2 \sim len$中的每一个值。

2. 每个字符都相同，则答案为$0$。

3. 是交错型的字符串，则$k$可以取$2 \sim len$中的每一个偶数。

4. 只是回文串，则$k$可以取$2 \sim {len - 1}$中的每一个值。

   判断回文串使用了双Hash（好久没用过了，写一个规范点的出来用）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

#include <bits/stdc++.h>
#include <chrono>
#include <random>
using namespace std;

const int N = 200010;
namespace RAND {
    unsigned int SEED() {
        auto now = chrono::system_clock::now();
        auto timestamp = chrono::duration_cast<chrono::milliseconds>(now.time_since_epoch());
        return static_cast<unsigned int>(timestamp.count());
    }
    mt19937 R(SEED());
} // namespace RAND

unsigned long long mod1 = RAND::R(), mod2 = RAND::R();
class HASH {
    typedef unsigned long long ull;
    typedef pair<ull, ull> pULL;
public:
    ull base, pow1[N], pow2[N];
    vector<ull> hash1, hash2;
    HASH() {
        base = 27;
        pow1[0] = pow2[0] = 1;
        for (int i = 1; i < N; ++i) {
            pow1[i] = (pow1[i - 1] * base) % mod1;
            pow2[i] = (pow2[i - 1] * base) % mod2;
        }
    }
    // 默认字符串从1开始
    void init(string s) {
        int len = s.size() - 1;
        hash1.reserve(s.size()), hash2.reserve(s.size());
        hash1[0] = hash2[0] = 0;
        for (int i = 1; i <= len; ++i) {
            hash1[i] = (hash1[i - 1] * base + s[i] - 'a') % mod1;
            hash2[i] = (hash2[i - 1] * base + s[i] - 'a') % mod2;
        }
    }
    pULL subHash(int l, int r) {
        if (l == 1) return make_pair(hash1[r], hash2[r]);
        pULL tmp;
        tmp.first = (hash1[r] - hash1[l - 1] * pow1[r - l + 1] % mod1 + mod1) % mod1;
        tmp.second = (hash2[r] - hash2[l - 1] * pow2[r - l + 1] % mod2 + mod2) % mod2;
        return tmp;
    }
} hashFront, hashBack;

int n, q;
string s;
void work() {
    cin >> n >> q;
    cin >> s;
    hashFront.init(" " + s);
    reverse(s.begin(), s.end());
    hashBack.init(" " + s);
    reverse(s.begin(), s.end());
    int len = s.size();
    s = " " + s;
    unsigned long long ans, L;
    vector<int> id(n + 1); // 判断交错
    id[1] = 1, id[2] = 2;
    for (int i = 3; i <= len; i++) {
        if (s[i] == s[i - 2]) id[i] = id[i - 2];
        else id[i] = i;
    }
    vector<int> con(n + 1); // 判断连续
    con[1] = 1;
    for (int i = 2; i <= len; i++) {
        if (s[i] == s[i - 1]) con[i] = con[i - 1];
        else con[i] = i;
    }
    for (int i = 1, l, r; i <= q; ++i) {
        cin >> l >> r;
        L = (r - l + 1);
        if (L == 1) {
            cout << "0\n";
            continue;
        }
        if (L == 2) {
            if (s[l] == s[r]) cout << "0\n";
            else cout << "2\n";
            continue;
        }
        auto x1 = hashFront.subHash(l, r);
        auto x2 = hashBack.subHash(len - r + 1, len - l + 1);
        if (x1 == x2) {
            bool flag = 1;
            if (con[r] == con[l]) {
                cout << 0 << '\n';
                continue;
            }
            if (id[l] == id[r] && id[l + 1] == id[r - 1]) {
                unsigned long long tmp = (L / 2) * 2;
                ans = (2 + tmp) * (L / 2) / 2;
            } else {
                ans = (1 + L - 1) * (L - 1) / 2 - 1;
            }
        } else {
            if (id[l] == id[r - 1] && id[l + 1] == id[r]) {
                ans = (2 + L) * L / 4;
            } else ans = (2 + L) * (L - 1) / 2;
        }
        cout << ans << '\n';
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
        work();
    return 0;
}