Description

You have to place N queens on a NxN chessboard in such a way that no queen threatens another one

The rule is that each row and column of the board contains exactly 1 queen , and each diagonal contains no more than 1 queen.

Your mission is to compute how many possible ways to place N queens on that chessboard.

Input

An integer N which represent the size of chessboard and the number of queens.

where 1<=N<=10

Output

An integer which represent the number of possible distributions of  N queens.

There is no need to add '\n' at the end of output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Last time, you build a hacker script that hack the system password.

So the system's protection were strengthen after your attack.

 

This time, you also got the system password,

and the system's protection mechanism has replaced some consecutive letters into a '#',

or replaced some consecutive and identical letters into a '$' as the system settings.

 

After that, there will be zero to many '#' character and zero to many '$' character,

and each '#' character represent one to many arbitary letters,

each '$' character represent one to many identity letters.

 

For example, if the password is 'abcdefff',

then the system can replace 'a' to '#', replace 'def' to '#' and replace the last 2 'f' to '$',

the the password will become '#bc#$'.

 

To get the whole control of the system,

you must know the exactly letters replaced by each '#' and '$'.

 

Now, your goal is to find the number of combinations for all '#' and '$'.

 

ouo.

 

For Sample Input 1, 3 possibles combinations are:

(#₁, #₂, #₃) = (b, cde, g), (bc, de, g), (bcd, e, g)

 

For Sample Input 2, 4 possibles combinations are:

($₁, $₂) = (aaaa, a), (aaa, aa), (aa, aaa), (a, aaaa)

 

For Sample Input 3, 2 possibles combinations are:

($₁, #₁, $₂) = (b, baaa, b), (bb, aaa, b)

 

Input

The first line of input contains an integer T,

represents that there are T testcases.

 

For each testcase contains 2 lines of input data,

There first line contains a string S, represent the password of the system.

The second line contains a string P, represent the string you get after the system replaced some character from S to '#' or '$'.

 

It is guaranteed that:

1 <= T <= 10,

1 <= |S| <= 20, and S contains only lowercase letters,

1 <= |P| <= 20, and P contains only lowercase letters, '#' or '$'.

And there must be at least 1 '#' or '$' in P.

 

For testcase 1 and 2, there is no '$' character in P.

For testcase 3, there is no '#' character in P.

Output

For each testcase,

output contains only 1 line,

the number of combinations for all '#' and '$' with a newline character.

 

Note that the number of combinations may be zero.

Sample Input  Download

Sample Output  Download

Tags

Discuss