The Mahabharata is an epic narrative of the Kurukshetra War and the fates of the Kaurava and the Pandava princes. Arjuna was the 3rd of the Pandava brothers. He is considered the protagonist of the Mahabharata with Krishna. Abhimanyu was the son of Arjuna and Subhadra. Abhimanyu's story came to prominence on the 13th day of the war when he entered the powerful Chakravyuha battle formation of the Kaurava army. Drona had designed this configuration in order to capture Yudhishthira. On the side of the Pandavas, only Krishna and Arjuna were aware of the secret technique to break this seven-tier, defensive, spiral formation.

Seeing Yudhishthira's panic, Abhimanyu revealed that while he didn't know how to exit the formation, he would be able to break into it. A plan was formulated that the Pandava forces would enter the Chakravyuha after Abhimanyu, and shatter it from within. But as soon as Abhimanyu entered the Chakravyuha, Jayadratha stopped the four Pandavas from entering it. At last Abhimanyu was killed inside the Chakravyuha. The news of Abhimanyu's death reached his father Arjuna at the end of the day. Arjuna vowed to kill Jayadratha the very next day by sunset, and failing to do so, would commit suicide by self-immolation immediately. So Arjuna has to reach Jayadratha before sunset.

There are N spots in the Kauravas army numbered from 0 to N-1. Arjuna was always at spot 0 and Jayadratha was always at spot 1. He need to reach the spot '1' as soon as possible killing the soldiers of the army. The time to reach each spot is given in the form of N x N array. Also Arjuna had 'K' Divyastras (Divine arrow) which halves the time (only take half of what it normally would) to reach any spots. Arjuna was not allowed to use more than one Divyastras at same time. He may or may not use Divyastra. Find the smallest time in which Arjuna can reach Jayadratha.

Input

First line T the number of test cases. (T<=55)

Second line N the number of spots in the battle. (2<=N<=50)

Next N*N matrix indicates the time to reach other spots. (Each value in the matrix <=50)

K the number of Divyastras Arjuna had initially. (0<=K<=50)

Output

A Single value indicating the minimum time required to reach Jayadratha.

Example

Input:
1
3
0 9 4
9 0 4
4 4 0
1

Output:
4.5

Explanation

According to given data, you need:

• 9 units of time to move between spots 0 and 1.
• 4 units of time to move between spots 0 and 2.
• 4 units of time to move between spots 1 and 2.
• You have a single Divyastra.

The optimal solution is to use a Divyastra and move directly from spot 0 to spot 1. This will take 9/2 = 4.5 units of time.