EC_WORLD - Rotations

no tags 

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

hide comments
Sandip Jana: 2015-06-28 13:07:29

Learned a new Thing in JAVA..Thanks To Problem Setter

Eddy Cael: 2014-09-11 02:08:39

I am sorry for wrong constraint. Somebody from Spoj's EB change my problem statement. Lenght p <= 10^5.

Bhavik: 2014-09-11 02:08:39

@Eddy Cael: Can you kindly tell why my code id:12304418 gives internal error!!
Is it due to logic or something else?

LeppyR64: 2014-09-11 02:08:39

Confirmed 100%. There is a test case with |P| == 100000. All test cases have |P| <= 100000.

wisfaq: 2014-09-11 02:08:39

please remove unnecesary language restrictions.

RIVU DAS: 2014-09-11 02:08:39

I request the problem setter to change the constraints ASAP!

mehmetin: 2014-09-11 02:08:39

length P is greater than 10000 in the input, I guess it is 100000 maximum.

Last edit: 2014-09-01 09:38:24

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