在一个神秘的字母王国，所有的字母都有其独特的魅力。每当一个字符串的第一个字符和最后一个字符相同时，它就被称为“美丽的”。这个王国的居民们喜欢通过旋转字符串来寻找美丽的字符串。

给定一个长度为n的字符串，定义一个操作 表示将字符串S向左旋转d次后得到的新字符串。具体来说。

你需要找出最小的非负整数d，使得f(S,d)是美丽的。如果不存在这样的 ，则输出 -1。

解释：

f(S,3)=nmddxdagn。由于它的第一个字符和最后一个字符都是 ，因此它是一个美丽的字符串。虽然  也是美丽的，但我们需要返回最小的非负整数 。所以答案是 。

数据范围

• 
  

  
  对于30% 的数据n<=13，
  

  
  


• 
  

  
  对于50%的数据n<=5*10^4，
  

  
  


• 
  

  
  对于100%的数据n<=2*10^6，
  

  
  

字符串