有一串长度为 n 的核桃，每个核桃上有一个字母，从第一个核桃开始盘，盘完最后一个又回 到第一个，盘每个核桃的时候会读出对应的字母。有一个长度为 m 的咒语，依次读出咒语 的每一个字母后可以获得一个奖励，问获得 k 个奖励需要盘多少次核桃
| Time Limit | $1$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $4$ | 正确数量 | $1$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 |
有一串长度为 n 的核桃，每个核桃上有一个字母，从第一个核桃开始盘，盘完最后一个又回 到第一个，盘每个核桃的时候会读出对应的字母。有一个长度为 m 的咒语，依次读出咒语 的每一个字母后可以获得一个奖励，问获得 k 个奖励需要盘多少次核桃
第一行输入一个整数 T，代表有 T 组测试数据 对于每一组测试数据，第一行输入三个整数 n, m, k，第二行输入 2 个字符串 s1, s2，分别表示核桃上的字母和咒语
1 ≤ T ≤ 10
1 ≤ n ≤ 105
1 ≤ m ≤ 105
1 ≤ k ≤ 1012
字符串中只含有小写英文字母
对于每组测试数据，输出盘核桃的次数，如果不能完成输出-1
4
5 3 2
ououo ouo
6 3 2
ououou ouo
2 5 1
ou ououo
3 4 1
ouo ouou
8
7
5
-1
对于前三组样例的解释:
ououo ououo
ououou ououou
| 本题记录 | 用 户（点击查看用户） | 运行号（点击购买题解） | 时 间 |
|---|---|---|---|
| 算法最快[$391 $ms] | RUBY-WOO | 591274 | 2020-06-06 20:38:51 |
| 内存最少[$4624 $KB] | RUBY-WOO | 591274 | 2020-06-06 20:38:51 |
| 第一AC | RUBY-WOO | 591274 | 2020-06-06 20:38:51 |
| 第一挑战 | RUBY-WOO | 591251 | 2020-06-06 18:35:51 |
| 竞赛编号 | 竞赛名称 | 竞赛时间 | 访问比赛 |
|---|