In this problem, we assume that the Earth is a perfect sphere.

For two positions on the equator, the west distance  is defined as the distance from to if you keep going west, the east distance  is defined as the distance from to if you keep going east.

We called is to the west of if , is to the east of if . Noticed that  might be neither to the west nor to the east of .¶

A direction matrix  is defined as a matrix satisfying these conditions:

• For each integer such that , .
• For each integer pair such that and , .

A direction matrix  is real if there are  distinct positions on the equator satisfying these conditions:

• All points meet the anticlockwise order when we look down at the equator from above the north pole.
• For each integer pair such that and , if , is to the west of , otherwise is to the east of .

Now you are given a direction matrix , but some and are replaced by . If you can replace each by or , how many real direction matrix you can get? Print the number modulo .

Each test contains multiple test cases. The first line contains the number of test cases  (). Description of the test cases follows.

The first line contains a single integer  ().

Then  lines follow. The -th of these lines contains a string  of length  consisting of , describing the direction matrix .

It is guaranteed that the sum of  over all test cases does not exceed .

For each test case, output a single line contains a single integer, indicating the answer modulo .

3
3
*W?
?*?
?E*
4
*???
?*??
??*?
???*
5
*W???
?*W??
??*W?
???*?
????*

2
8
13

Here is the explanation of the first test case when we look down at the equator from above the north pole.