Abhi and his friends (Shanky,Anku and Pandey) love to play with strings. Abhi invented a simple game. He will give a string S to his friends. Shanky and Anku will play the game while Pandey is just a spectator. Shanky will traverse the string from beginning (left to right) while Anku will traverse from last (right to left). Both have to find the first character they encounter during their traversal,that appears only once in the entire string. Winner will be one whose character is alphabetically more superior(has higher ASCII value). When it is not possible to decide the winner by comparing their characters, Pandey will be the winner.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

Each test case contains a string S having only lowercase alphabets ( a..z ).

-----Output-----
For each test case, output a single line containing "SHANKY" if Shanky is the winner or "ANKU" if Anku is the winner or "PANDEY" if the winner is Pandey. Output your answer without quotes.

-----Constraints-----
- 1 ≤ T ≤ 100
- 1 < |S| ≤ 10^5

-----Example-----
Input:
3
google
breakraekb
aman

Output:
SHANKY
PANDEY
ANKU

-----Explanation-----
Example case 2. Both Shanky and Anku can not find any such character. Hence it is not possible to decide the winner between these two. So Pandey is the winner.

Difficulty: interview

Starter code:

Solutions:
t = int(input())

for e in range(t):

 str = input()

 dict = {}

 for x in range(len(str)):
  if str[x] in dict:
   dict[str[x]] = -1
  else:
   dict[str[x]] = x

 shankyIndex = len(str)
 ankuIndex = -1
 for x in dict:
  if dict[x] != -1:
   if dict[x] < shankyIndex:
    shankyIndex = dict[x]
   if dict[x] > ankuIndex:
    ankuIndex = dict[x]

 ankuLetter = 0
 shankyLetter = 0

 if ankuIndex != -1:
  ankuLetter = str[ankuIndex]
 else:
  print('PANDEY')
  continue

 if shankyIndex != len(str):
  shankyLetter = str[shankyIndex]
 else:
  print('PANDEY')
  continue

 if shankyLetter > ankuLetter:
  print('SHANKY')
 elif ankuLetter > shankyLetter:
  print('ANKU')
 else:
  print('PANDEY')

t = int(input())

for e in range(t):

 str = input()

 dict = {}

 for x in range(len(str)):
  if str[x] in dict:
   dict[str[x]] = -1
  else:
   dict[str[x]] = x

 shankyIndex = len(str)
 ankuIndex = -1
 for x in dict:
  if dict[x] != -1:
   if dict[x] < shankyIndex:
    shankyIndex = dict[x]
   if dict[x] > ankuIndex:
    ankuIndex = dict[x]

 ankuLetter = 0
 shankyLetter = 0

 if ankuIndex != -1:
  ankuLetter = str[ankuIndex]
 else:
  print('PANDEY')
  continue

 if shankyIndex != len(str):
  shankyLetter = str[shankyIndex]
 else:
  print('PANDEY')
  continue

 if shankyLetter > ankuLetter:
  print('SHANKY')
 elif ankuLetter > shankyLetter:
  print('ANKU')
 else:
  print('PANDEY')

for _ in range(int(input())):
 a = [0]*26
 s = input()
 t = s[::-1]
 for c in s:
  a[ord(c)-ord('a')]+=1
 l = []
 for i in range(26):
  if (a[i]==1):
   l.append(chr(ord('a')+i))
 if (len(l)<=1):
  print("PANDEY")
 else:
  shan = ""
  for c in s:
   if (c in l):
    shan = c
    break
  anku = ""
  for c in t:
   if (c in l):
    anku = c
    break
  if (shan>anku):
   print("SHANKY")
  else:
   print("ANKU")