Gambler

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

Alice and Bob are going to play a game. Before the game starts, each of them will
write down a string which only consists of "1" and "0". For convenience, the Alice\'s
string will be marked as P and the Bob\'s string will be marked as Q.
Then, they will toss a coin by (at most) K times. The i-th tossing result S i is "1" if the
coin turns face up, otherwise it will be "0". During the game, if the Alice\'s string P or
the Bob\'s string Q exists in the current tossing sequence, the game will end
immediately. If only P appears in the tossing sequence, Alice will win the game. If
only Q appears, Bob will win. If both P and Q appears at the same time, or none of
them appears after K times of coin tossing, the game is draw.
Given P, Q and K, please calculate the winning probability of Alice and Bob
respectively. The coin is uniform, so any tossing result has an equal probability to be
"1" or "0".

Input

There are multiple test cases. The first line of input contains an integer T indicating
the number of test cases. For each test case:
The first line and the second line contains two non-empty strings P and Q. The length
of each string will not exceed 10.
The last line contains an integer K (1 <= K <= 50).

Output

 For each test case, output a line with 2 numbers representing the winning probability
of Alice and Bob respectively.
Any solution with a relative or absolute error of at most 1e-6 will be accepted.

Sample Input

2
010
001
25
0
11
5

Sample Output

0.33310899 0.66596049
0.75000000 0.25000000

Hint

 

Source

Ningbo_2014_Contest