시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB49243002269962.870%

문제

당신은 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 개가 된다.

W3sicHJvYmxlbV9pZCI6IjU1NTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMThcdWM5YzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjJmOVx1YzJlMFx1Yzc0MCBOXHVhYzFjXHVjNzU4IFx1YmMxOFx1YzljMFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHViYzE4XHVjOWMwXHViMjk0Jm5ic3A7XHViMzAwXHViYjM4XHVjNzkwIDEwIFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzBjOFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YmMxOFx1YzljMFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVjMmRjXHVjNzkxXHVhY2ZjIFx1YjA1ZFx1Yzc3NCBcdWM1ZjBcdWFjYjBcdWI0MWMgXHVkNjE1XHVkMGRjXHViODVjIFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWMwYzhcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LiBcdWJjMThcdWM5YzBcdWM1ZDAgXHVhYzAxXHVjNzc4XHViNDFjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWFjNzBcdWFmYjhcdWI4NWMgXHVjNzdkXHViMjk0IFx1YWM3MVx1YzgxNVx1Yzc0MCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2MzZVx1YWNlMFx1Yzc5MFx1ZDU1OFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YyBcdWFkZjggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YjI5NCBcdWJjMThcdWM5YzBcdWFjMDAgXHViYTg3IFx1YWMxY1x1Yzc3OFx1YzljMFx1Yjk3YyBcdWJjMWNcdWFjYWNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWNkMWQgMiArIE4gXHVjOTA0IFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgMSBcdWM3OTAgXHVjNzc0XHVjMGMxIDEwIFx1Yzc5MCBcdWM3NzRcdWQ1NThcdWM3NTggXHViMzAwXHViYjM4XHVjNzkwXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxYyBcdWNjM2VcdWFjZTBcdWM3OTAgXHVkNTU4XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4MDFcdWQ2MDBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmMxOFx1YzljMFx1Yzc1OCBcdWFjMWNcdWMyMTggTiAoMSBcdTIyNjYgTiBcdTIyNjYgMTAwKVx1Yzc3NCBcdWM4MDFcdWQ2MDBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjIraSZuYnNwO1x1YzkwNCgxIFx1MjI2NiBpIFx1MjI2NiBOKVx1YzVkNCZuYnNwO2lcdWFjMWNcdWM3NTggXHViYzE4XHVjOWMwXHVjNWQwIFx1YzBjOFx1YWNhOFx1YzgzOFx1Yzc4OFx1YWNlMCwmbmJzcDsxMCBcdWJiMzhcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4MDFcdWQ2MDBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjYzNlXHVhY2UwXHVjNzkwXHVkNTU4XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWQzZWNcdWQ1NjggXHViYzE4XHVjOWMwXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjODE1XHVjMjE4XHViOTdjIFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiI8cD4mbHQ7XHVjNjA4XHVjODFjIFx1Yzc4NVx1YjgyNSZuYnNwOzImZ3Q7XHVjNzU4IFx1YmMxOFx1YzljMFx1YzVkMFx1YjI5NCAmcXVvdDtYWVomcXVvdDtcdWI3N2NcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YjRcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YWM4M1x1Yzc0MCBcdWJjMThcdWM5YzBcdWM3NTggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YzJkY1x1Yzc5MVx1YWNmYyBcdWIwNWRcdWM3NzQgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiZsdDtcdWM2MDhcdWM4MWMgXHVjNzg1XHViODI1IDMmZ3Q7XHVjNzU4IFx1Y2NhYiZuYnNwO1x1YmM4OFx1YzlmOCBcdWJjMThcdWM5YzBcdWIyOTQgJnF1b3Q7UFFSJnF1b3Q7XHVjNzc0XHViNzdjXHViMjk0IFx1YjJlOFx1YzViNFx1YWMwMCAyIFx1YWMxYyBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YjQgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YmMxOFx1YzljMFx1YjI5NCAmcXVvdDtQUVImcXVvdDtcdWI3N2NcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IDEgXHVhYzFjIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNCBcdWM3ODhcdWM3M2NcdWJhNzAsJm5ic3A7XHVjMTM4IFx1YmM4OFx1YzlmOCBcdWJjMThcdWM5YzBcdWM1ZDBcdWIyOTQgJnF1b3Q7UFFSJnF1b3Q7XHViNzdjXHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YjQgXHVjNzg4XHVjOWMwIFx1YzU0YVx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjICZxdW90O1BRUiZxdW90O1x1Yjc3Y1x1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVkM2VjXHVkNTY4XHViNDE4XHVjNWI0XHVjNzg4XHViMjk0IFx1YmMxOFx1YzljMFx1Yzc1OCBcdWMyMThcdWIyOTQgMiBcdWFjMWNcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNTU1NSIsInByb2JsZW1fbGFuZyI6IjIiLCJ0aXRsZSI6Ilx1NjMwN1x1OGYyYSAoUmluZykiLCJkZXNjcmlwdGlvbiI6IjxwPlx1MzA0Mlx1MzA2YVx1MzA1Zlx1MzA2ZiBOIFx1NTAwYlx1MzA2ZVx1NjMwN1x1OGYyYVx1MzA5Mlx1NjMwMVx1MzA2M1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZSBcdTMwNjlcdTMwNmVcdTYzMDdcdThmMmFcdTMwNmJcdTMwODJcdWZmMGNcdTMwYTJcdTMwZWJcdTMwZDVcdTMwYTFcdTMwZDlcdTMwYzNcdTMwYzhcdTMwNmVcdTU5MjdcdTY1ODdcdTViNTcgMTAgXHU2NTg3XHU1YjU3XHUzMDRiXHUzMDg5XHUzMDZhXHUzMDhiXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDRjXHU1MjNiXHU1MzcwXHUzMDU1XHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlIFx1NjMwN1x1OGYyYVx1MzA2Ylx1MzA2Zlx1NjU4N1x1NWI1N1x1NTIxN1x1MzA2ZVx1NjcwMFx1NTIxZFx1MzA2OFx1NjcwMFx1NWY4Y1x1MzA0Y1x1MzA2NFx1MzA2YVx1MzA0Y1x1MzA2M1x1MzA1Zlx1NWY2Mlx1MzA2N1x1NjU4N1x1NWI1N1x1MzA0Y1x1NTIzYlx1NTM3MFx1MzA1NVx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZSBcdTYzMDdcdThmMmFcdTMwNmJcdTUyM2JcdTUzNzBcdTMwNTVcdTMwOGNcdTMwNWZcdTY1ODdcdTViNTdcdTUyMTdcdTMwOTJcdTkwMDZcdTk4MDZcdTMwNmJcdThhYWRcdTMwODBcdTVmYzNcdTkxNGRcdTMwNmZcdTMwNmFcdTMwNDRcdWZmMGU8XC9wPlxyXG5cclxuPHA+XHU2M2EyXHUzMDU3XHUzMDVmXHUzMDQ0XHU2NTg3XHU1YjU3XHU1MjE3XHUzMDRjXHU0ZTBlXHUzMDQ4XHUzMDg5XHUzMDhjXHUzMDVmXHUzMDY4XHUzMDRkXHVmZjBjXHUzMDVkXHUzMDZlXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDkyXHU1NDJiXHUzMDgwXHU2MzA3XHU4ZjJhXHUzMDRjXHU0ZjU1XHU1MDBiXHUzMDQyXHUzMDhiXHUzMDRiXHUzMDkyXHU2YzQyXHUzMDgxXHUzMDhiXHUzMGQ3XHUzMGVkXHUzMGIwXHUzMGU5XHUzMGUwXHUzMDkyXHU0ZjVjXHU2MjEwXHUzMDViXHUzMDg4XHVmZjBlPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdTUxNjVcdTUyOWJcdTMwNmYgMitOIFx1ODg0Y1x1MzA0Ylx1MzA4OVx1MzA2YVx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD4xIFx1ODg0Y1x1NzZlZVx1MzA2Ylx1MzA2Zlx1ZmYwYzEgXHU2NTg3XHU1YjU3XHU0ZWU1XHU0ZTBhIDEwIFx1NjU4N1x1NWI1N1x1NGVlNVx1NGUwYlx1MzA2ZVx1MzBhMlx1MzBlYlx1MzBkNVx1MzBhMVx1MzBkOVx1MzBjM1x1MzBjOFx1MzA2ZVx1NTkyN1x1NjU4N1x1NWI1N1x1MzA0Ylx1MzA4OVx1MzA2YVx1MzA4Ylx1NjNhMlx1MzA1N1x1MzA1Zlx1MzA0NFx1NjU4N1x1NWI1N1x1NTIxN1x1MzA0Y1x1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD4yIFx1ODg0Y1x1NzZlZVx1MzA2Ylx1MzA2Zlx1ZmYwY1x1NjMwN1x1OGYyYVx1MzA2ZVx1NTAwYlx1NjU3MCBOICggMSBcdTIyNjYgTiBcdTIyNjYgMTAwIClcdTMwNGNcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+MitpIFx1ODg0Y1x1NzZlZSgxIFx1MjI2NiBpIFx1MjI2NiBOIClcdTMwNmJcdTMwNmZcdWZmMGMgaSBcdTUwMGJcdTc2ZWVcdTMwNmVcdTYzMDdcdThmMmFcdTMwNmJcdTUyM2JcdTUzNzBcdTMwNTVcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGIgMTAgXHU2NTg3XHU1YjU3XHUzMDRiXHUzMDg5XHUzMDZhXHUzMDhiXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHU2M2EyXHUzMDU3XHUzMDVmXHUzMDQ0XHU2NTg3XHU1YjU3XHU1MjE3XHUzMDkyXHU1NDJiXHUzMDgwXHU2MzA3XHU4ZjJhXHUzMDZlXHU1MDBiXHU2NTcwXHUzMDkyXHU4ODY4XHUzMDU5XHU2NTc0XHU2NTcwXHUzMDkyIDEgXHU4ODRjXHUzMDY3XHU1MWZhXHU1MjliXHUzMDViXHUzMDg4XHVmZjBlPFwvcD5cclxuIiwiaGludCI6IjxwPlx1NTE2NVx1NTI5Ylx1NGY4YiAyIFx1MzA2ZVx1NjMwN1x1OGYyYVx1MzA2Ylx1MzA2Zlx1MzAwY1hZWlx1MzAwZFx1MzA2OFx1MzA0NFx1MzA0Nlx1NjU4N1x1NWI1N1x1NTIxN1x1MzA0YyAxIFx1MzA2NFx1NTQyYlx1MzA3ZVx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZVx1MzA1M1x1MzA4Y1x1MzA2Zlx1MzAwMVx1NjMwN1x1OGYyYVx1MzA2ZVx1NjU4N1x1NWI1N1x1NTIxN1x1MzA2ZVx1NjcwMFx1NTIxZFx1MzA2OFx1NjcwMFx1NWY4Y1x1MzA0Y1x1MzA2NFx1MzA2YVx1MzA0Y1x1MzA2M1x1MzA2Nlx1MzA0NFx1MzA4Ylx1MzA1Zlx1MzA4MVx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD5cdTUxNjVcdTUyOWJcdTRmOGIgMyBcdTMwNmUgMSBcdTUwMGJcdTc2ZWVcdTMwNmVcdTYzMDdcdThmMmFcdTMwNmJcdTMwNmZcdTMwMGNQUVJcdTMwMGRcdTMwNjhcdTMwNDRcdTMwNDZcdTY1ODdcdTViNTdcdTUyMTdcdTMwNGMgMiBcdTMwNjRcdTU0MmJcdTMwN2VcdTMwOGNcdTMwNjZcdTMwNGFcdTMwOGFcdWZmMGMgMiBcdTUwMGJcdTc2ZWVcdTMwNmVcdTYzMDdcdThmMmFcdTMwNmJcdTMwNmZcdTMwMGNQUVJcdTMwMGRcdTMwNjhcdTMwNDRcdTMwNDZcdTY1ODdcdTViNTdcdTUyMTdcdTMwNGMgMSBcdTUwMGJcdTU0MmJcdTMwN2VcdTMwOGNcdTMwNjZcdTMwNGFcdTMwOGFcdWZmMGMgMyBcdTUwMGJcdTc2ZWVcdTMwNmVcdTYzMDdcdThmMmFcdTMwNmJcdTMwNmZcdTMwMGNQUVJcdTMwMGRcdTMwNjhcdTMwNDRcdTMwNDZcdTY1ODdcdTViNTdcdTUyMTdcdTMwNGNcdTU0MmJcdTMwN2VcdTMwOGNcdTMwNjZcdTMwNDRcdTMwNmFcdTMwNDRcdWZmMGUgXHUzMDVkXHUzMDZlXHUzMDVmXHUzMDgxXHUzMDBjUFFSXHUzMDBkXHUzMDY4XHUzMDQ0XHUzMDQ2XHU2NTg3XHU1YjU3XHU1MjE3XHUzMDRjXHU1NDJiXHUzMDdlXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHU2MzA3XHU4ZjJhXHUzMDZlXHU2NTcwXHUzMDZmIDIgXHU1MDBiXHUzMDY4XHUzMDZhXHUzMDhiXHVmZjBlPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJKYXBhbmVzZSJ9XQ==