URI Online Judge | 1756

Genetic Algorithm

By Victor Marcilio Peixoto, UNIVASF BR Brazil

Timelimit: 1

Some computer science courses are too much theorical and sometimes boring. In an attempt to raise the students' interest in some topics, the Artificial Intelligence professor, always when possible, propose a challenging contemplating the topics seen in class that day.

Today's lecture was about genetic algorithms and the professor explained the following procedure:

From 2 individuals (two sequences of N bits: x0x1...xN-1) A and B, we choose a cut position Y ( 1 ≤ Y < N) and the crossover process happens, creating 2 new individuals: the first one is the concatenation of bits x0...xY-1 from individual A followed by bits xY..xN-1 from individual B, the second one is the concatenation of bits x0...xY-1 from individual B followed by bits xY..xN-1 from individual A.

The following image shows the result of a crossover with Y = 5.

After the crossover, each bit from the brand-new individuals may suffer mutation (change its value) according to a specified mutation probability P.

The challenge's statement left by the professor was the following:

"Write a program that takes as input 3 individuals, the cutting position and the mutation probability. The program must calculate the probability of obtaining the third individual as a result of a crossover between the other two."

Input

The first line of input contains an integer T (1 ≤ T ≤ 50), the number of test cases.

Each test case takes 5 lines.

The first line contains an integer N (2 ≤ N ≤ 8), the number of bits in each individual.

The second line contains an integer Y (1 ≤ Y < N) followed by a floating-point number P (0 ≤ P ≤ 1), the cut position and the mutation probability, respectively.

The third line contains the first individual to be crossedover.

The fourth line contains the second individual to be crossedover.

The fifth line contains the individual that will be compared to the possible crossover results.

Output

For each test case output a single line containing the answer with 7 digits after the decimal point.

Input Sample Output Sample

4
3
2 0
111
111
111
2
1 0.5
11
11
10
4
2 0.1
1010
0001
1111
2
1 0.1
11
11
11

1.0000000
0.4375000
0.0089927
0.9639000