Rings

Interview

Time limit1sMemory limit128 MB

Summary

Count how many of N rings, each a 10-letter circular string, contain a given search string when read around the circle.

Level: Easy3 of 10
Topics: String, String matching, Implementation, Brute force
Solved: No attempts yet

Problem

You have $N$ rings. Each ring has a string of $10$ uppercase letters engraved on it. The engraved string is circular: its start and end are joined, so it is read around the ring. You never read the string in reverse.

Given a search string, write a program that counts how many rings contain that string when the ring is read as a circle.

Input

The first line contains the search string, whose length is between $1$ and $10$ and which consists of uppercase letters only.

The second line contains the number of rings $N$ ( $1 \le N \le 100$ ).

Each of the next $N$ lines contains a string of $10$ uppercase letters engraved on a ring; the $i$ -th of these lines describes the $i$ -th ring.

Output

Print a single integer on one line: the number of rings that contain the search string.

Hint

Because a ring's string is joined end to start, the search string may appear by wrapping from the end back to the beginning. For example, the ring ZAAAAAAAXY contains XYZ once when read as a circle (the trailing XY is followed by the leading Z).

Also, even if the search string appears several times on one ring, that ring is counted only once. For example, PQRAAAAPQR contains PQR twice but counts as a single ring.

Examples3

Example 1

Input

ABCD
3
ABCDXXXXXX
YYYYABCDXX
DCBAZZZZZZ

Expected output

Example 2
Input
```
XYZ
1
ZAAAAAAAXY
```
Expected output
```
1
```

Example 3

Input

PQR
3
PQRAAAAPQR
BBPQRBBBBB
CCCCCCCCCC

Expected output