Rotate the String

Problem code: ROTSTRNG

All submissions for this problem are available.

Did you know that a cluster of bananas can also be called a 'hand' of bananas ? No points for guessing what the individual bananas are called. ya.. 'fingers' :). The monkey from the valley of food is all set to fight for the title 'Dragon Chef' after having a hand of bananas for breakfast. As you know that the judge, master Oogway is always late for the show, the monkey and Po decided to play a game. They took a string of characters and started rotating it.

A k-rotation on a string takes the trailing k characters of the string and attaches it to the beginning of the string in the same order. For eg. 3-rotation on the string "noodles" results in the string "lesnood". On the given string S, the monkey performs a M-rotation and gives it to Po. Po performs a P-rotation on it and gives back to the monkey. The monkey again performs a M-rotation on it and so on... Though Shifu is getting angry watching the monkey play with Po, he is wondering after how many minimum (non-zero) number of rotations we can get back to the original string S. This can happen after a rotation performed by the monkey or Po. Please find it for him.

Input

First line contains T ( number of test cases, around 10 ). T cases follow. Each case consists of two lines. First line has the string S of length n ( 1 <= n <= 500,000 ), having ('a'-'z' , 'A'-'Z'). Second line contains two integers M P separated by a space ( 1 <= M, P <= n ). Comparisons are case sensitive i.e., 'a' is not equal to 'A'.

Output

For each test case, output the answer in a new line. If its impossible to get back to the original string by performing the rotations as mentioned above, print -1

Example

Input:
2
AbcDef
1 2
abcabc
1 1

Output:
4
3


Explanation
Case 1 :
Monkey : fAbcDe , Po : DefAbc, Monkey : cDefAb , Po : AbcDef

Case 2 :
Monkey : cabcab , Po : bcabca, Monkey : abcabc

Warning : Large input / output. You may have to use efficient input / output methods if you are using languages with heavy input / output overload. Eg: Prefer using scanf/printf to cin/cout for C/C++

Author: flying_ant
Date Added: 6-08-2011
Time Limit: 2 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

we have to give input of all

shanal @ 21 Aug 2011 10:58 PM
we have to give input of all the cases at the starting??? can we not process 1 case and then giv the input of other.....

@shanal: You can certainly do

harsha_adm @ 21 Aug 2011 11:06 PM
@shanal: You can certainly do that.

even the output..? i mean

skyrockvishesh @ 21 Aug 2011 11:29 PM
even the output..? i mean printing the output before taking the input of the next test case?

@skyrockvishesh: yes you can

harsha_adm @ 21 Aug 2011 11:36 PM
@skyrockvishesh: yes you can do that

i have a doubt about input

sushant_ingle @ 27 Aug 2011 11:22 AM
i have a doubt about input string.would it contain space? because they have given wrong ans result for my submission and my program does not support space in string.

plz reply

sushant_ingle @ 27 Aug 2011 11:23 AM
plz reply

@sushant_ingle: it is written

wil93 @ 27 Aug 2011 04:05 PM
@sushant_ingle: it is written "..string S ... having ('a'-'z' , 'A'-'Z').." so the string shouldn't contain spaces

Any way by which I can submit

kartikrustagi @ 29 Aug 2011 11:36 PM
Any way by which I can submit solutions to this problem now? (just to get my solution checked)

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions