FILRTEST - File Recover Testing

In a recent programming contest appeared a problem named “File Recover”. In that problem, repeated strings of a given text were to be counted. You are preparing test cases for that problem, and in order to test for border cases you want to generate a text with many repetitions of a particular string. Of course, test cases cannot be arbitrarily long, so you decided to choose a length and a string, and then fit in a text of that length as many repetitions as possible of the string.

For instance, if the length is 14 and the string is “abcab”, you may generate the text “abcabcabcabcab” whose length is 14 and where the string “abcab” appears 4 times (starting at positions 1, 4, 7 and 10).

You would like to know how good your idea is before implementing. Given a length and a string, you must determine the maximum number of times the characters of the string can appear consecutively in a text of that length.

Input

Each test case is described using a single line. The line contains an integer K (1 ≤ K ≤ 109 ) and a non-empty string S of at most 106 lowercase letters. The end of input is indicated with a line containing the number −1 and an asterisk (“*”).

Output

For each test case, output a single line with a single integer representing the maximum number of times the characters of S can appear consecutively in a text of length K.

Example

Input:
14 abcab
1000 abcde
1000000000 z
1 zzzzz
-1 *

Output:
4
200
1000000000
0

Added by:Pablo Ariel Heiber
Date:2010-09-27
Time limit:1.975s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 NODEJS OBJC VB.NET
Resource:FCEyN UBA ICPC Selection 2010

hide comments
2024-10-18 04:14:33
AC testcase:
5 abcd
-1 *
1
beware of partial match!
2018-05-03 15:59:33
Nice KMP Problem. Just build the KMP pre-processing array & then just simple calculation.
2017-10-20 18:57:36
Any test case ?
2017-09-22 16:56:41 Sigma Kappa
#greedy, #KMP
2017-02-03 11:30:29
AC in 1 go :-)
2016-12-16 13:13:15
nice one taught new Z algo
2016-11-01 07:23:31
try these
14 abca
14 abab
15 ababa
27 foobarfoo
-1 *
2 WA's due to miscomprehension of the question. KMP :D

2015-05-15 07:41:21 geetha
Am getting WA even thought it worked on my machine..any idea?
2015-04-01 21:00:30 arp_ee
easy kmp !!
2012-08-29 05:03:19 Ajey Golsangi
Nice problem.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.