BBB（Byteotian Bit Bank 的缩写）拥有 Byteotia 最大的自动取款机网络。BBB 的客户可以使用银行卡和 4 位 PIN 码从取款机中提取现金。最近，为了提高客户的安全性，BBB 在每台取款机旁都安装了摄像头。摄像头通过无线电信号将录制的图像传输给 BBB。不幸的是，这些信号正被一群电脑窃贼拦截。窃贼试图发现 BBB 客户的 4 位 PIN 码，并随后窃取他们的银行卡。意识到这一点后，BBB 的客户在输入 PIN 码时会尝试进行多余的按键动作。摄像头无法识别具体的按键，只能记录手指的移动轨迹。因此，通常无法明确确定 PIN 码。例如，客户的手指先经过按键 1，然后经过按键 5，他可能输入的 PIN 码包括：1111, 1115, 1155, 1555, 5555。绝望的窃贼收集了摄像头的录像，指望能够确定客户的 PIN 码，或者至少根据多次交易记录限制可能的代码数量。在积累了某位富有的 BBB 客户输入的序列后，他们向你提出了一个“无法拒绝的提议”。

编写一个程序：

• 从标准输入读取客户在输入 PIN 码时所执行的手指移动序列描述；
• 确定客户可能拥有的不同 PIN 码的数量（即通过执行给定的手指移动序列可能输入的 4 位 PIN 码的数量）；
• 将结果写入标准输出。

输入

标准输入的第一行包含一个整数 $n$，表示记录的客户输入 PIN 码的场景数量，$1 \le n \le 1,000$。接下来的 $n$ 行每行描述一个场景。每个场景的描述由两个正整数组成，中间用空格隔开。第一个数字 $t$ 表示移动序列的长度，$1 \le t \le 10,000$。另一个是一个 $t$ 位的数字，其连续的数字表示客户手指经过的连续按键。所有序列的总长度不超过 $1,000,000$。

输出

输出的第一行也是唯一一行应包含一个正整数，即客户可能的 PIN 码数量。

样例

输入格式 1

2
3 123
3 234

输出格式 1

5