贴近生活的吃鸡问题

Time Limit: 2000 ms

Memory Limit: 262144 KB

Description

  由于某些原因,戴老板又双叒叕要和吉吉玩游戏决定谁请客吃鸡了。
  他们翻字典得到了n个只有小写字母的单词。游戏刚开始他们有一个空的字符串,他们轮流往字符串后面添加一个字母。添加后的字符串必须是找出来的单词中至少一个的前缀,率先无法添加的人会输掉游戏。   由于戴老板运气一向不错,吉吉不愿意一局定胜负。他提出要进行k场游戏,每一场输掉的人下一场先手开始,输掉最后一场的人请客吃鸡。   现在单词已经选好,戴老板突然有点慌。他想请你编程序算一算,他应该先走还是后走,才能让吉吉请客吃鸡。   PS.戴老板和吉吉当然都很聪明,他们总能做出最优决策。

Input

  第一行一个T,表示样例数。   对于每个样例,第一行两个正整数n,k(1≤n≤1e5;1≤k≤1e9)分别表示单词数和游戏轮数。   接下来n行,每行有一个非空字符串,一个样例中所有字符串的总长度不超过1e5。   字符串只包含小写英文字母。

Output

  如果戴老板应该先手,输出 "First",否则输出"Second" 。

Sample Input

1
2 3
ab
ba

Sample Output

Second

Hint

  每一轮先手都必输无疑。持续三轮……

Source

None

提交代码