403154: GYM101047 J The Kamphaeng Phet's Chedis

J. The Kamphaeng Phet's Chedistime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

A chedi (also known as stupa, dagoba, or pagoda) is a relic usually shaped as a conic tower built over the remains of someone Buddhists consider important. Some historical Thai sites have dozens such structures, dedicated to monks or nuns or other religious leaders (known as bhikkhu - ภกษณ, in Thailand). For instance, in Kamphaeng Phet some chedi inscriptions refer to Garuda (ครฑ), and similarly in Si Satchanalai and Sukhothai.

The differences between some Thai symbols are very subtle, making it hard for experts to analyze words. For instance, when any symbol of the word Ramakien (รามเกยรต) is changed, its meaning is altered completely. Since many of the sites are over 700 years old, the inscriptions are very worn.

An example is the pair of inscriptions below, found in distinct chedis:

จดษตงขนโดยพรภะบมพธานญาษ

จดตงขโกดยพระบรมษพทธานญาต

Experts believe both refer to the same entity. They developed a method to validate their hypothesis; this is called the method of minimum probabilistic difference.

The method works as follows. Let a = a₁ a₂... a_N and b = b₁ b₂... b_M be two inscriptions with N and M characters, respectively. The parameter called difference is initially set to zero. At each step, we analyze a pair (a_i, b_j) of characters with 1 ≤ i ≤ N + 1 and 1 ≤ j ≤ M + 1, starting with (a₁, b₁). Assume a_N + 1 and b_M + 1 are null characters.

During each step, there are four possible actions you can take:

• Change the current pair to (a_i + 1, b_j + 1). This must be done iff i ≤ N, j ≤ M, and a_i = b_j.
• Change the current pair to (a_i + 1, b_j) and increase the difference by 1. This can only be done if i ≤ N.
• Change the current pair to (a_i, b_j + 1) and increase the difference by 1. This can only be done if j ≤ M.
• Increase the difference by K and change the current pair to (a_x, b_y). The values x and y are chosen randomly in the intervals [i + 1 . . N + 1] and [j + 1 . . M + 1], respectively. Each value in the interval has the same probability of being chosen. If i = N + 1, then i does not change. If j = M + 1, then j does not change.

The analysis ends after when the pair (a_N + 1, b_M + 1) is processed. Note that the difference parameter may vary with the choices made in the procedure.

The experts consider that, the smaller the computed difference, the higher correspondence between the inscriptions. They want you to write a program to compute the minimum expected difference between two inscriptions.

Input

The first line has a single integer T, the number of test cases.

Each test case starts with 3 integers N, M, and K, where N is the length of the first inscription and M is the length of the second inscription. The next two lines contain, respectively, the first and second inscription. An inscription is a string of characters from a to z.

Limits

• 1 ≤ T ≤ 500
• 1 ≤ N, M ≤ 3·10³
• The sum of N and M over all test cases will not exceed 1.2·10⁴.
• 0 ≤ K ≤ 10⁵

Output

For each test case, print a real number, the minimum expected difference between two inscriptions. The error should not exceed 10^- 4.

ExampleInput

3
3 3 2
aab
aba
4 3 0
abcc
eee
2 3 1
ab
cba

Output

2.0000000000
0.0000000000
1.9166666667