2096 : 起名字

        As we all know,名字是一个人很重要的符号。很多时候名字带有时代意义或者期望意义，比如王富贵，李漂亮，刘跃进，

周卫红等等。现在呢，人们的文化素质有了很大的提高，名字也就随之更加富有寓意。换句话说，人们不想让名字里带有看上去

就很直接的词汇，如翠花富贵一类。那么问题来了，现在有人来找你让你帮忙取一个长度为n的名字，用他给你的字符，并且组成

的名字中不能含有他不想要的词汇，请问能组成多少个名字呢？

第一行一个T代表测试用例(T<=10)

第二行一个n(1<=n<=1e9)

第三行一个只包含小写字母的字符串s1(length(s1)<=26)，代表起名字可用的字符, 每个字符可以重复使用多次。

第三行也是一个只包含小写字母的字符串s2（length(s2)<=50），代表名字中不能出现的词汇（名字中不能出现此字符串）。

一个数字，代表可组成长度为n的名字的个数，结果对2的32次方取余。

3
3
ab
ab
4
acd
ca
5
ab
aaa

4
55
24