### 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

#### Source

Ningbo_2014_Contest