在 Harie 大学，你必须在通过课程注册系统之前通过一份课程行为准则测验。

该测验共有 10 道选择题，每题有四个选项（‘A’、‘B’、‘C’、‘D’）。每道题只有一个正确答案。每答对一题得 10 分，答错不得分。你需要获得满分（100 分）才能通过测验。你可以多次尝试测验，且每份测验的题目集保持不变。当你完成测验时，系统会告诉你最终得分，但不会告诉你具体哪些题目答对了。

你已经多次尝试该测验失败，现在想根据之前的观察结果，计算出有多少种可能的答案组合。更具体地说，给定之前测验尝试中选择的选项和得分，计算在所有可能的选项组合中，有多少种组合仍然是可能的。

题目保证输入数据是一致的，即至少存在一种可能的答案。

输入格式

输入包含多个独立的测试用例。第一行包含一个整数 $t$ ($1 \le t \le 20000$)，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$ ($1 \le n \le 20000$)，表示测验的次数。

接下来的 $n$ 行描述了这些测验的结果。每行包含一个字符串 $s$ ($|s| = 10, s_i \in \{‘A’, ‘B’, ‘C’, ‘D’\}$) 和一个整数 $a$ ($0 \le a \le 90, a$ 是 10 的倍数)，两者以空格分隔。$s$ 的第 $i$ 个字符表示第 $i$ 道题所选的选项，$a$ 表示测验得分。

输入文件中所有 $n$ 的总和不超过 20000。

输出格式

对于每个测试用例，输出一个整数，表示可能的答案数量。

样例

样例输入 1

3
1
CCCCCCCCCC 90
2
AAAAAAAAAA 10
ABCDABCDAB 20
3
AAAAAAAAAA 0
BBBBBBBBBB 0
CCCCCCCCCC 0

样例输出 1

30
57456
1