Soundex 是一种将字符串转换为代码的语音算法，代码始终由一个字母后跟三个数字组成。其目的是将拼写不同但发音相似的字符串转换为相同的代码。转换规则如下：

• 字符串的第一个字母即为代码的第一个字母。
• 随后的辅音字母替换为数字：
  • b, f, p, v 替换为 1
  • c, g, j, k, q, s, x, z 替换为 2
  • d, t 替换为 3
  • l 替换为 4
  • m, n 替换为 5
  • r 替换为 6 h 和 w 被忽略。元音字母 a, e, i, o, u 和 y 不进行编码。
• 两个或多个相邻且对应相同数字的字母被替换为一个数字。两个或多个对应相同数字的字母如果被 h 或 w 分隔，也会被替换为一个数字。如果两个对应相同数字的字母被元音分隔，则该数字会出现两次。
• 重复上述步骤，直到无法再将重复的数字合并为一个数字。
• 如果生成的代码不足 3 位数字，则在末尾补零，直到代码达到 3 位数字。如果超过 3 位数字，则舍弃最右侧的数字。

一些转换示例如下：

• robert 和 rupert 都转换为 R163。
• baawwwww 转换为 B000。
• hopp 转换为 H100。字符串的第一个字母始终成为代码的第一个字母，即使它是元音、h 或 w。
• ratatata 转换为 R333，因为每对 t (3) 之间的元音强制该数字重复。
• yhhhwthwhtwhthwhwth 转换为 X300。所有 h 和 w 均被忽略，代码中仅保留一个 3。
• bbpb 转换为 B100。第一个 b 与后三个 b 分开。剩余的 b 是连续的，被替换为一个数字。

你的邪恶朋友 Halvor 注意到许多不同的单词会产生相同的 Soundex 代码。例如，字符串 rhhhbm、rubeno、rpowam、robnew 以及其他 73908 个长度为 6 或更短的字符串都会被转换为代码 R150。这让他非常好奇，他想知道有多少个长度为 $L$ 或更短的字符串会被转换为相同的 Soundex 代码。当然，他希望你编写一个计算机程序来完成这项任务。你的朋友不关心大小写，因此 AA、Aa、aa 等被视为相同的字符串，且只能计数一次。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。每个测试用例以一行开始，包含一个字符串 $S$ 和一个整数 $L$。$S$ 表示一个 Soundex 代码，由一个大写字母后跟三个数字组成。$L$ 表示转换为给定 Soundex 代码的原始字符串的最大长度。

输出格式

对于每个测试用例，输出一行，包含一个数字，表示长度为 $L$ 或更短且具有 Soundex 代码 $S$ 的字符串数量。该数字可能很大，请输出其对 $1,000,000,007$ 取模的结果。

数据范围

• $0 < T \le 100$
• $0 < L \le 1000$
• 所有 Soundex 代码均以大写字母开头。
• 如果两个字符串 $S$ 和 $T$ 长度相同，且对应位置的字母相同（不区分大小写），则它们相等。
• 仅考虑 a 到 z 之间的字母。不使用 æ, ø, å 或其他非英文字符。
• Soundex 代码始终合法。即非零数字永远不会跟在零数字后面，且数字范围为 0 到 6。

样例

输入格式 1

3
A300 2
R150 6
X123 1

输出格式 1

2
73912
0