C-BJS and HT_第五届石家庄铁道大学程序设计竞赛

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$BJS$ and $HT$ have known each other for more than $100$ days, but $BJS$ doesn't have the courage to confess. $BJS$ decides to estimate the success rate of his own confession. In other words, $BJS$ and $HT$ can be matched to several groups in $N$ groups of conditions. Each group has two strings. The string of $BJS$ is $B$ and the string of $HT$ is $H$ . if H can be obtained by intercepting $K$ consecutive characters from $B$ and putting them in the front, it is considered that this group of $BJS$ and $HT$ has been matched successfully, For $N$ groups of data, please output the number of successful matching groups.

输入描述:

The first line is an integer $N$ $(N<=100000)$ , which represents the number of condition groups

Followed by several lines, each line has two strings and an integer, representing $B$ , $H$ and $K$ $(K<=6)$ respectively.

sum of the string length is less than $1e8$ ，single string length is less than $5e5$

输出描述:

An integer indicating the number of groups successfully matched

示例1

输入

复制

10
fztclsb clsfztb 3
fztclsb lsbfztc 3
fztclsb tclfzsb 3
fztclsb clsfztb 3
fztclsb fztclsb 3
fztclsb clsfzbt 3
fztclsb clfsztb 3
fztclsb tclfszb 3
fztclsb lbsfztc 3
fztclsb lcsfztb 3

输出

复制

说明

The first 5 groups were matched successfully, while the last 5 groups failed

示例2

输入

复制

10
32286513581 51358322861 5
32286513581 28651323581 5
32286513581 13581322865 5
32286513581 86513322581 5
32286513581 65135322881 5
32286513581 35813228651 5
32286513581 35813228651 5
32286513581 22863513581 5
32286513581 51353228681 5
32286513581 86513223581 5

输出

复制

说明

The first 5 groups are matched successfully, while the last 5 groups fail
(the last 5 groups correspond to 4 consecutive characters, so they do not meet the meaning of the question)