+2 x2

초깃값이 $2$인 변수 $X$와, 길이 $N$의 문자열 $S$가 있다. $S$는 A와 M으로만 이루어져있다.

각 글자에 대해서 A일 시 $X$에 $2$가 더해지며, M일 시 $X$에 $2$가 곱해진다. 각 연산을 진행할 때마다, $2^k$가 $X$의 약수가 되는 가장 큰 양의 정수 를 출력하라.

첫 줄에 길이 $N$ ($\leq 10^6$)의 문자열 $S$가 주어진다.

$i$번째 줄 $(1 \leq i \leq N)$ 에 첫 $i$개의 연산을 한 뒤의 정답인 양의 정수를 출력한다.

• $N \leq 10^6$
• $S$는 A와 M으로만 이루어져있다.