시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 651 347 309 57.435%

문제

당신은 N 개의 반지를 가지고있다. 어떤 반지도 대문자 10 문자로 이루어진 문자열이 새겨져있다. 반지는 문자열의 시작과 끝이 연결된 형태로 문자가 새겨져있다. 반지에 각인된 문자열을 거꾸로 읽는 걱정은 없다.

찾고자하는 문자열이 주어졌을 때 그 문자열을 포함하는 반지가 몇 개인지를 발견하는 프로그램을 작성하라.

입력

입력은 2 + N 행된다.

첫 번째 줄에는 1 자 이상 10 자 이하의 대문자로 구성된 찾고자하는 문자열이 적혀있다.

두 번째 줄에는 반지의 개수 N (1 ≦ N ≦ 100)이 적혀있다.

2+i 줄(1 ≦ i ≦ N)엔 i개의 반지에 새겨져있고, 10 문자로 이루어진 문자열이 적혀있다.

출력

찾고자하는 문자열을 포함 반지의 개수를 나타내는 정수를 한 줄로 출력하라.

예제 입력 1

ABCD
3
ABCDXXXXXX
YYYYABCDXX
DCBAZZZZZZ

예제 출력 1

2

예제 입력 2

XYZ
1
ZAAAAAAAXY

예제 출력 2

1

예제 입력 3

PQR
3
PQRAAAAPQR
BBPQRBBBBB
CCCCCCCCCC

예제 출력 3

2

힌트

<예제 입력 2>의 반지에는 "XYZ"라는 문자열이 하나 포함되어있다. 이것은 반지의 문자열의 시작과 끝이 연결되어 있기 때문이다.

<예제 입력 3>의 첫 번째 반지는 "PQR"이라는 단어가 2 개 포함되어 있으며, 두 번째 반지는 "PQR"라는 문자열이 1 개 포함되어 있으며, 세 번째 반지에는 "PQR"라는 문자열이 포함되어 있지 않다. 따라서 "PQR"라는 문자열이 포함되어있는 반지의 수는 2 개가 된다.

W3sicHJvYmxlbV9pZCI6IjU1NTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMThcdWM5YzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjJmOVx1YzJlMFx1Yzc0MCBOIFx1YWMxY1x1Yzc1OCBcdWJjMThcdWM5YzBcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwXHVjNzg4XHViMmU0LiBcdWM1YjRcdWI1YTQgXHViYzE4XHVjOWMwXHViM2M0IFx1YjMwMFx1YmIzOFx1Yzc5MCAxMCBcdWJiMzhcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWMwYzhcdWFjYThcdWM4MzhcdWM3ODhcdWIyZTQuIFx1YmMxOFx1YzljMFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVjMmRjXHVjNzkxXHVhY2ZjIFx1YjA1ZFx1Yzc3NCBcdWM1ZjBcdWFjYjBcdWI0MWMgXHVkNjE1XHVkMGRjXHViODVjIFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWMwYzhcdWFjYThcdWM4MzhcdWM3ODhcdWIyZTQuIFx1YmMxOFx1YzljMFx1YzVkMCBcdWFjMDFcdWM3NzhcdWI0MWMgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YWM3MFx1YWZiOFx1Yjg1YyBcdWM3N2RcdWIyOTQgXHVhYzcxXHVjODE1XHVjNzQwIFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjYzNlXHVhY2UwXHVjNzkwXHVkNTU4XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjIFx1YWRmOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVkM2VjXHVkNTY4XHVkNTU4XHViMjk0IFx1YmMxOFx1YzljMFx1YWMwMCBcdWJhODcgXHVhYzFjXHVjNzc4XHVjOWMwXHViOTdjIFx1YmMxY1x1YWNhY1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIDIgKyBOIFx1ZDU4OVx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgMSBcdWM3OTAgXHVjNzc0XHVjMGMxIDEwIFx1Yzc5MCBcdWM3NzRcdWQ1NThcdWM3NTggXHViMzAwXHViYjM4XHVjNzkwXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxYyBcdWNjM2VcdWFjZTBcdWM3OTBcdWQ1NThcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYzE4XHVjOWMwXHVjNzU4IFx1YWMxY1x1YzIxOCBOICgxIFx1MjI2NiBOIFx1MjI2NiAxMDApXHVjNzc0IFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+MitpJm5ic3A7XHVjOTA0KDEgXHUyMjY2IGkgXHUyMjY2IE4pXHVjNWQ0Jm5ic3A7aVx1YWMxY1x1Yzc1OCBcdWJjMThcdWM5YzBcdWM1ZDAgXHVjMGM4XHVhY2E4XHVjODM4XHVjNzg4XHVhY2UwLCZuYnNwOzEwIFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjM2VcdWFjZTBcdWM3OTBcdWQ1NThcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1ZDNlY1x1ZDU2OCBcdWJjMThcdWM5YzBcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM4MTVcdWMyMThcdWI5N2MgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IjxwPiZsdDtcdWM2MDhcdWM4MWMgXHVjNzg1XHViODI1Jm5ic3A7MiZndDtcdWM3NTggXHViYzE4XHVjOWMwXHVjNWQwXHViMjk0ICZxdW90O1hZWiZxdW90O1x1Yjc3Y1x1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVkNTU4XHViMDk4IFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHVhYzgzXHVjNzQwIFx1YmMxOFx1YzljMFx1Yzc1OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVjMmRjXHVjNzkxXHVhY2ZjIFx1YjA1ZFx1Yzc3NCBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+Jmx0O1x1YzYwOFx1YzgxYyBcdWM3ODVcdWI4MjUgMyZndDtcdWM3NTggXHVjY2FiJm5ic3A7XHViYzg4XHVjOWY4IFx1YmMxOFx1YzljMFx1YjI5NCAmcXVvdDtQUVImcXVvdDtcdWM3NzRcdWI3N2NcdWIyOTQgXHViMmU4XHVjNWI0XHVhYzAwIDIgXHVhYzFjIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHViYzE4XHVjOWMwXHViMjk0ICZxdW90O1BRUiZxdW90O1x1Yjc3Y1x1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgMSBcdWFjMWMgXHVkM2VjXHVkNTY4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YzczY1x1YmE3MCwmbmJzcDtcdWMxMzggXHViYzg4XHVjOWY4IFx1YmMxOFx1YzljMFx1YzVkMFx1YjI5NCAmcXVvdDtQUVImcXVvdDtcdWI3N2NcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNCBcdWM3ODhcdWM5YzAgXHVjNTRhXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgJnF1b3Q7UFFSJnF1b3Q7XHViNzdjXHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YjRcdWM3ODhcdWIyOTQgXHViYzE4XHVjOWMwXHVjNzU4IFx1YzIxOFx1YjI5NCAyIFx1YWMxY1x1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1NTU1IiwicHJvYmxlbV9sYW5nIjoiMiIsInRpdGxlIjoiXHU2MzA3XHU4ZjJhIiwiZGVzY3JpcHRpb24iOiI8cD5cdTMwNDJcdTMwNmFcdTMwNWZcdTMwNmYgTiBcdTUwMGJcdTMwNmVcdTYzMDdcdThmMmFcdTMwOTJcdTYzMDFcdTMwNjNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGUgXHUzMDY5XHUzMDZlXHU2MzA3XHU4ZjJhXHUzMDZiXHUzMDgyXHVmZjBjXHUzMGEyXHUzMGViXHUzMGQ1XHUzMGExXHUzMGQ5XHUzMGMzXHUzMGM4XHUzMDZlXHU1OTI3XHU2NTg3XHU1YjU3IDEwIFx1NjU4N1x1NWI1N1x1MzA0Ylx1MzA4OVx1MzA2YVx1MzA4Ylx1NjU4N1x1NWI1N1x1NTIxN1x1MzA0Y1x1NTIzYlx1NTM3MFx1MzA1NVx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZSBcdTYzMDdcdThmMmFcdTMwNmJcdTMwNmZcdTY1ODdcdTViNTdcdTUyMTdcdTMwNmVcdTY3MDBcdTUyMWRcdTMwNjhcdTY3MDBcdTVmOGNcdTMwNGNcdTMwNjRcdTMwNmFcdTMwNGNcdTMwNjNcdTMwNWZcdTVmNjJcdTMwNjdcdTY1ODdcdTViNTdcdTMwNGNcdTUyM2JcdTUzNzBcdTMwNTVcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGUgXHU2MzA3XHU4ZjJhXHUzMDZiXHU1MjNiXHU1MzcwXHUzMDU1XHUzMDhjXHUzMDVmXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDkyXHU5MDA2XHU5ODA2XHUzMDZiXHU4YWFkXHUzMDgwXHU1ZmMzXHU5MTRkXHUzMDZmXHUzMDZhXHUzMDQ0XHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1NjNhMlx1MzA1N1x1MzA1Zlx1MzA0NFx1NjU4N1x1NWI1N1x1NTIxN1x1MzA0Y1x1NGUwZVx1MzA0OFx1MzA4OVx1MzA4Y1x1MzA1Zlx1MzA2OFx1MzA0ZFx1ZmYwY1x1MzA1ZFx1MzA2ZVx1NjU4N1x1NWI1N1x1NTIxN1x1MzA5Mlx1NTQyYlx1MzA4MFx1NjMwN1x1OGYyYVx1MzA0Y1x1NGY1NVx1NTAwYlx1MzA0Mlx1MzA4Ylx1MzA0Ylx1MzA5Mlx1NmM0Mlx1MzA4MVx1MzA4Ylx1MzBkN1x1MzBlZFx1MzBiMFx1MzBlOVx1MzBlMFx1MzA5Mlx1NGY1Y1x1NjIxMFx1MzA1Ylx1MzA4OFx1ZmYwZTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHU1MTY1XHU1MjliXHUzMDZmIDIrTiBcdTg4NGNcdTMwNGJcdTMwODlcdTMwNmFcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+MSBcdTg4NGNcdTc2ZWVcdTMwNmJcdTMwNmZcdWZmMGMxIFx1NjU4N1x1NWI1N1x1NGVlNVx1NGUwYSAxMCBcdTY1ODdcdTViNTdcdTRlZTVcdTRlMGJcdTMwNmVcdTMwYTJcdTMwZWJcdTMwZDVcdTMwYTFcdTMwZDlcdTMwYzNcdTMwYzhcdTMwNmVcdTU5MjdcdTY1ODdcdTViNTdcdTMwNGJcdTMwODlcdTMwNmFcdTMwOGJcdTYzYTJcdTMwNTdcdTMwNWZcdTMwNDRcdTY1ODdcdTViNTdcdTUyMTdcdTMwNGNcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+MiBcdTg4NGNcdTc2ZWVcdTMwNmJcdTMwNmZcdWZmMGNcdTYzMDdcdThmMmFcdTMwNmVcdTUwMGJcdTY1NzAgTiAoIDEgXHUyMjY2IE4gXHUyMjY2IDEwMCApXHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPjIraSBcdTg4NGNcdTc2ZWUoMSBcdTIyNjYgaSBcdTIyNjYgTiApXHUzMDZiXHUzMDZmXHVmZjBjIGkgXHU1MDBiXHU3NmVlXHUzMDZlXHU2MzA3XHU4ZjJhXHUzMDZiXHU1MjNiXHU1MzcwXHUzMDU1XHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiIDEwIFx1NjU4N1x1NWI1N1x1MzA0Ylx1MzA4OVx1MzA2YVx1MzA4Ylx1NjU4N1x1NWI1N1x1NTIxN1x1MzA0Y1x1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1NjNhMlx1MzA1N1x1MzA1Zlx1MzA0NFx1NjU4N1x1NWI1N1x1NTIxN1x1MzA5Mlx1NTQyYlx1MzA4MFx1NjMwN1x1OGYyYVx1MzA2ZVx1NTAwYlx1NjU3MFx1MzA5Mlx1ODg2OFx1MzA1OVx1NjU3NFx1NjU3MFx1MzA5MiAxIFx1ODg0Y1x1MzA2N1x1NTFmYVx1NTI5Ylx1MzA1Ylx1MzA4OFx1ZmYwZTxcL3A+XHJcblxyXG4iLCJoaW50IjoiPHA+XHU1MTY1XHU1MjliXHU0ZjhiIDIgXHUzMDZlXHU2MzA3XHU4ZjJhXHUzMDZiXHUzMDZmXHUzMDBjWFlaXHUzMDBkXHUzMDY4XHUzMDQ0XHUzMDQ2XHU2NTg3XHU1YjU3XHU1MjE3XHUzMDRjIDEgXHUzMDY0XHU1NDJiXHUzMDdlXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlXHUzMDUzXHUzMDhjXHUzMDZmXHUzMDAxXHU2MzA3XHU4ZjJhXHUzMDZlXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDZlXHU2NzAwXHU1MjFkXHUzMDY4XHU2NzAwXHU1ZjhjXHUzMDRjXHUzMDY0XHUzMDZhXHUzMDRjXHUzMDYzXHUzMDY2XHUzMDQ0XHUzMDhiXHUzMDVmXHUzMDgxXHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1NTE2NVx1NTI5Ylx1NGY4YiAzIFx1MzA2ZSAxIFx1NTAwYlx1NzZlZVx1MzA2ZVx1NjMwN1x1OGYyYVx1MzA2Ylx1MzA2Zlx1MzAwY1BRUlx1MzAwZFx1MzA2OFx1MzA0NFx1MzA0Nlx1NjU4N1x1NWI1N1x1NTIxN1x1MzA0YyAyIFx1MzA2NFx1NTQyYlx1MzA3ZVx1MzA4Y1x1MzA2Nlx1MzA0YVx1MzA4YVx1ZmYwYyAyIFx1NTAwYlx1NzZlZVx1MzA2ZVx1NjMwN1x1OGYyYVx1MzA2Ylx1MzA2Zlx1MzAwY1BRUlx1MzAwZFx1MzA2OFx1MzA0NFx1MzA0Nlx1NjU4N1x1NWI1N1x1NTIxN1x1MzA0YyAxIFx1NTAwYlx1NTQyYlx1MzA3ZVx1MzA4Y1x1MzA2Nlx1MzA0YVx1MzA4YVx1ZmYwYyAzIFx1NTAwYlx1NzZlZVx1MzA2ZVx1NjMwN1x1OGYyYVx1MzA2Ylx1MzA2Zlx1MzAwY1BRUlx1MzAwZFx1MzA2OFx1MzA0NFx1MzA0Nlx1NjU4N1x1NWI1N1x1NTIxN1x1MzA0Y1x1NTQyYlx1MzA3ZVx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA2YVx1MzA0NFx1ZmYwZSBcdTMwNWRcdTMwNmVcdTMwNWZcdTMwODFcdTMwMGNQUVJcdTMwMGRcdTMwNjhcdTMwNDRcdTMwNDZcdTY1ODdcdTViNTdcdTUyMTdcdTMwNGNcdTU0MmJcdTMwN2VcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdTYzMDdcdThmMmFcdTMwNmVcdTY1NzBcdTMwNmYgMiBcdTUwMGJcdTMwNjhcdTMwNmFcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+XHUyMDNiXHU1NDA0XHU1MTY1XHU1MWZhXHU1MjliXHU0ZjhiXHUzMDZlXHUzMGM3XHUzMGZjXHUzMGJmXHUzMDZmXHVmZjBjIFx1NTNmM1x1MzBhZlx1MzBlYVx1MzBjM1x1MzBhZlx1N2I0OVx1MzA2Ylx1MzA4OFx1MzA4YVx1MzBkNVx1MzBhMVx1MzBhNFx1MzBlYlx1MzA2Ylx1NGZkZFx1NWI1OFx1MzA1N1x1MzA2Nlx1NTIyOVx1NzUyOFx1NTNlZlx1ODBmZFx1MzA2N1x1MzA1OVx1ZmYwZTxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNzdjXHViY2Y4XHVjNWI0In1d