SP12612 RIOI_2_3 - Path of the righteous man

You are given N\*N matrix A filled with integers, which represents map of country "What" ("What" ain't no country I ever heard of) . Our hero is called Brett. Brett has many enemies, namely Jules and Vincent (Jules doesn't like him because he said "what" too many times), but his biggest enemy is Marcellus Wallace, because Brett treated him like a male dog treats female dog. And Marcellus most certainly does not look like a female dog. But Brett cannot sit at home all day enjoying his Big Kahuna burgers, he has to go from cell (sx, sy) to cell (ex, ey). From cell (x, y) Bret can go to (x+1, y), (x, y+1), (x-1, y), (x, y-1). If A\[x\]\[y\] = S, we say that this cell is property of mafia boss S. When Brett visits cell (x, y), and has not yet apologised to boss A\[x\]\[y\], then he apologizes, after that he can visit any cell controlled by A\[x\]\[y\] without apologizing. Brett does not like to apologise ( because there is always chance to hear Ezekiel 25 17 ), so he asks you to find him path which minimizes number of times he has to apologise. You are given N\*N matrix A filled with integers, which represents map of country "What" ("What" ain't no country I ever heard of) . Our hero is called Bret. Bret has many enemies, namely Jules and Vincent (Jules doesn't like him because he said "what" too many times), but his biggest enemy is Marcellus Wallace, because Bret treated him like male dog treats female dog.

First line contains number t donating number of testcases. First line of each testcase consists of number N. N lines followscontaining N numbers donating matrix A. After that two lines follow, containing sx, sy and ex, ey.

For each test output number minimal number of times bret has to apologise.