완전 셔플 횟수

카드 한 벌을 섞는 방법 중에 완전 셔플이 있다. 완전 셔플은 카드 뭉치를 정확히 반으로 나눈 다음, 두 뭉치의 카드를 한 장씩 번갈아 끼워 넣는 방식이다.

카드 여덟 장으로 이루어진 ABCDEFGH를 예로 들자. A가 맨 위 카드다. 이 뭉치를 ABCD와 EFGH로 나눈 뒤 번갈아 끼우면 AEBFCGDH가 된다. 원래 맨 위에 있던 A가 그대로 맨 위에 남는 이 셔플을 아웃 셔플이라고 한다. 반대로 뒤쪽 절반의 첫 카드부터 놓으면 EAFBGCHD가 되고, 이 셔플은 인 셔플이라고 한다.

보통의 셔플과 달리 완전 셔플로 만들어지는 순서는 몇 가지뿐이다. 위의 여덟 장 뭉치에 아웃 셔플을 반복하면 ABCDEFGH, AEBFCGDH, ACEGBDFH, ABCDEFGH 순으로 바뀌어 세 번 만에 처음 순서로 돌아온다. 같은 뭉치에 인 셔플을 반복하면 여섯 번이 걸린다. 표준 52장 뭉치는 아웃 셔플 여덟 번이면 원래 순서로 돌아온다.

카드 장수가 홀수여도 완전 셔플을 할 수 있다. 다만 나누는 방법이 다르다. 아웃 셔플에서는 앞쪽 절반이 뒤쪽 절반보다 카드가 한 장 많고, 인 셔플에서는 그 반대다. 예를 들어 ABCDE에 아웃 셔플을 하면 ADBEC가 되고, 인 셔플을 하면 CADBE가 된다.

카드 장수와 셔플 종류가 주어졌을 때, 처음 순서로 돌아오려면 같은 셔플을 몇 번 해야 하는지 구하는 프로그램을 작성하시오.

첫째 줄에 카드 장수를 나타내는 정수 $n$ ($1 \le n \le 1000$)과 셔플 종류를 나타내는 문자열이 공백으로 구분되어 주어진다. 셔플 종류는 아웃 셔플이면 out, 인 셔플이면 in이다.

첫째 줄에 주어진 셔플을 반복해서 처음 순서로 돌아오기까지 필요한 셔플 횟수를 출력한다.