SP26119 THEWAR - Revenge of Arjuna

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 **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.

First line T the number of test cases.(T

A Single value indicating the minimum time required to reach Jayadratha