FILRTEST - File Recover Testing

no tags 

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

hide comments
flyingduchman_: 2018-05-03 15:59:33

Nice KMP Problem. Just build the KMP pre-processing array & then just simple calculation.

darkdreamofmy1: 2017-10-20 18:57:36

Any test case ?

Sigma Kappa: 2017-09-22 16:56:41

#greedy, #KMP

vengatesh15: 2017-02-03 11:30:29

AC in 1 go :-)

surajmall: 2016-12-16 13:13:15

nice one taught new Z algo

kushalanand: 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

geetha: 2015-05-15 07:41:21

Am getting WA even thought it worked on my machine..any idea?

arp_ee: 2015-04-01 21:00:30

easy kmp !!

Ajey Golsangi: 2012-08-29 05:03:19

Nice problem.

Pablo Ariel Heiber: 2010-09-27 23:27:20

File Recover is a problem of 2009 latin american regional: http://acm.uva.es/archive/nuevoportal/region.php?r=sa&year=2009


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