小猿有两张分别写着字符串s1、s2的纸条，字符串由大小写字母组成。小猿会进行n次操作，每次操作时小猿会选择其中一张纸条，把它从左侧撕下一段或把它全部交给你。你按收到纸条的顺序，从左到右将收到的n张纸条拼接成一张新的纸条。 已知字符串s1、s2，求是否存在一种方案使新纸条上的字符串与s3相同、且满足n

输入描述:

第一行输入T（T ≤ 20），表示输入T组数据。接下来T行，每行按顺序输入字符串s1、s2、s3和正整数K（K ≤ 50），用空格分开。字符串s1、s2长度不超过200，s3长度不超过400。

输出描述:

输出T行，每行输出对应组数据方案是否存在。存在输出1，不存在输出0。