In Computer Science, NAN stands for not a number, that can be interpreted as a value that is undefined. bruce developed a new language, named NAN language. There are two types of words in NAN language: A-word and B-word.

Every word that satisfies the following rules is an A-word.

• A single letter N is an A-word
• Given an A-word, replacing any letter N with NAN or NA will generate a new A-word

Every word that satisfies the following rules is a B-word.

• A single letter N is a B-word
• Given a B-word, replacing any letter N with NAN or NA or AN will generate a new B-word

Based on the above rules, can you write a program to check if a given word is an A-word or a B-word in NAN language?

Constraints

For all subtasks:

~1 \le |S| \le 10^6~

~T \le 10~

Subtask 1 [17%]

~|S| \le 40~

Subtask 2 [48%]

~|S| \le 2\,000~

Subtask 3 [35%]

No additional constraints.

Input Specification

The first line contains an integer ~T~, the number of test cases.

Each of the following ~T~ lines contains a string ~S~, only consisting of letters N and A.

Output Specification

Output ~T~ lines. Each line contains two integers ~a~ and ~b~. If the word is an A-word, ~a=1~; otherwise, ~a=0~. If the word is a B-word, ~b=1~; otherwise, ~b=0~.

Sample Input

4
NAN
ANN
ANAN
NANA

Sample Output

1 1
0 0
0 1
1 1