题目描述

给定一个长为 $n$ 的字符串

保证 $a$ 只包含 $1,2,3$ 三种字符。

你会做若干次操作。每次操作是选择 $a$ 的三个位置

使得 $(a_i,a_j,a_k)$ 严格单调增或严格单调减，然后删去这三个位置。

设删去的三元子序列中有 $x$ 个单调增，$y$ 个单调减，请求出有多少种可能的二元组 $(x,y)$。

输入格式

第一行，一个正整数 $t$，表示数据组数。

接下来，对于每组数据：

• 第一行，一个正整数 $n$；
• 第二行，一个长为 $n$ 的字符串 $a$。

输出格式

对于每组数据，输出一行一个正整数，表示可能的二元组 $(x,y)$ 的个数。

样例输入 #1

3
5
12321
14
12311311132133
12
121111321212

样例输出 #1

3
5
3

子任务

对于所有数据：