EC_WORLD - Rotations

Given a string S over the alphabet [a-z], the 'cyclic rotation' that chain is obtained by removing one or more characters from the beginning of the string and place them in the same order at the end of this. Eg. if S = 'abcd' some of its cyclic rotations are 'bcda' and 'dabc'. Given two strings P and Q, both of the same length, decide whether Q is a cyclic rotation of P.

Input

The first line contains an integer T, which represents the number of cases to solve. Each case consists of two lines, the first containing the string P and the second line contains the string Q.

T <= 100

length P <= 100000

Output

For each case should print 'Si' (without quotes) if the string Q is a cyclic rotation of P, and 'No' otherwise.

Example

Input:
2
abc
cab
aabb
abab

Output:
Si
No

Added by:Eddy Cael
Date:2014-08-31
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C CSHARP C++ 4.3.2 CPP JAVA PAS-FPC PYTHON RUBY
Resource:Internas UTO 2014

hide comments
2015-06-28 13:07:29 Sandip Jana
Learned a new Thing in JAVA..Thanks To Problem Setter
2014-09-11 02:08:39 Eddy Cael
I am sorry for wrong constraint. Somebody from Spoj's EB change my problem statement. Lenght p <= 10^5.
2014-09-11 02:08:39 Bhavik
@Eddy Cael: Can you kindly tell why my code id:12304418 gives internal error!!
Is it due to logic or something else?
2014-09-11 02:08:39 LeppyR64
Confirmed 100%. There is a test case with |P| == 100000. All test cases have |P| <= 100000.
2014-09-11 02:08:39 wisfaq
please remove unnecesary language restrictions.
2014-09-11 02:08:39 RIVU DAS
I request the problem setter to change the constraints ASAP!
2014-09-11 02:08:39 mehmetin
length P is greater than 10000 in the input, I guess it is 100000 maximum.

Last edit: 2014-09-01 09:38:24
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.