SUSTech Online Judge

Problem 1271 --Repeat!

1271: Repeat!

Time Limit: 1 Sec Memory Limit: 256 MB
Submit: 1050 Solved: 253
[Submit][Status][Web Board]

Description

Amayama finds that some "repeaters" have joined the computer science group. However, these people seem to update to the unordinary repeaters who only repeat part of the last sentence. Now, Amayama published some sentences in the group, and he wishes you to check out the number of "repeaters" who repeat him. He believes that if a person publishes a sentence that contains the prefix of the last one sentence, and this prefix is at least one-third the length of the last sentence (round up, e.g. for 100 then at least 34), then he is a "repeater".

Input

The first line contains a number N, which is the number of suspicious accounts. (1<=N<=1000) Then there are 2*N lines.

The 2*i-1 line is a string s, which is the sentence published by Amayama. (1<=|s|<=10000)

The 2*i line is a string p, which is the sentence published by a suspicious account. (1<=|p|<=10000)

Output

The output contains an integer, which is the number of repeaters.

Sample Input

2 
lanranwudi 
lanranwudi 
aaa
bbcc

Sample Output

HINT

The prefix of a string means a substring which must start from the first letter.

Source

[Submit][Status]