从前有一棵树，树上的每条边上都有一个小写字母。
有 次这样的询问：每次指出树上的两点 并给出一个由小写字母构成的字符串 ，询问串 在 中出现了多少次，其中 表示树上从点 到点 的唯一路径上每条边上的小写字母顺次连接形成的字符串。
注意 。
第一行两个正整数 。
接下来 行，每行两个正整数 和一个小写字母 ，表示一条树边 ，这条树边上的小写字母是 。
接下来 行，每两行表示一次询问。对于每次询问，第一行两个正整数 ，第二行一个由小写字符构成的字符串 ，意义详见题目描述。
输出 行表示每次询问的答案。
见附加文件
记 ，即输入的询问串总长度。
对于 的数据，
