^9(u

브론즈는 ^, v, 9, 6, (, ), u, n으로 이루어진 길이 $N$의 문자열을 선물받았다. 브론즈는 선물받은 문자열을 탐구하다가 문자열을 180도 돌리면 다음과 같이 바뀐다는 사실을 알아냈다.

1. 문자열의 순서가 뒤집힌다.
2. 다음과 같이 문자의 모양이 바뀐다.

• ^ → v
• v → ^
• 9 → 6
• 6 → 9
• ( → )
• ) → (
• u → n
• n → u

예를 들어 ^9(u를 180도 돌리면 n)6v가 되며, ^v96()un를 180도 돌리면 un()96^v가 된다.

부분 문자열은 문자열의 연속되어 나타나는 일부분을 말한다. 예를 들어 ^9(u에 등장하는 모든 부분 문자열은 ^, 9, (, u, ^9, 9(, (u, ^9(, 9(u, ^9(u이다.

브론즈는 제2회 AGCU컵 개최를 기념하려고 한다. 그래서 브론즈는 AgCu와 모양이 비슷한 ^9(u가 선물받은 문자열에 부분 문자열로 등장한 횟수를 최대화하려고 한다. 브론즈가 문자열을 180도 돌려야 할까?

첫 번째 줄에 브론즈가 선물받은 문자열의 길이를 나타내는 정수 N이 주어진다. 두 번째 줄에 브론즈가 선물받은 문자열이 주어진다.