Веднъж малкото бяло зайче, гонено от един ловец попаднало в лабиринт, които имал форма на квадратна дъска N x N. В него чакал големия лош вълк, които предварително изкопал дупки, където зайчето да падне и той да го хване по-лесно. В последния момент зайчето с ужас разбрало, че може да се движи само в 2 посоки - надолу и надясно и че изхода от лабиринта е чак в долния десен ъгъл на дъската. А то се намирало в горния ляв ъгъл :(
     Зайчето трябвало да разбере каква е вероятността да излезе от лабиринта без да падне в някоя дупка. За целта трябвало да изчисли броя пътища от входа до изхода на лабиринта, като успяло да се снабди с картата на този лабиринт. Картата е зададена с размер N, като местата на дупките са означени с 0, а проходимите места - с 1. Напишете програма F.EXE, която пресмята търсения брой пътища.
    Данните се четат от стандартния вход, където на първия ред е записано цялото число К – броя на тестовите примери, а за всеки тестов пример се подава числото N < 41 следват N реда с по  N числа, като на всяка клетка съответства по едно чило 1 или 0 (проходима клетка или дупка).
     На стандартния изход се извеждат К числа – по едно за всеки тестов пример, показващи броя на пътищата в съответния тестов пример. Всяко едно от числата се извежда на отделен ред.

Пример.