Given an nxn grid of cells, a bacteria colony can colonize these cells. Their growth after every second is governed by the following rules:

1. One new bacteria is born in cell (i, j) if and only if either one of its four neighboring cells or the cell (i, j) itself has a bacteria population more than or equal to the threshold value, k.
2. Already living bacteria do not die.

Given, the initial state of the nxn cell grid, you need to accurately estimate the time by when the total bacteria population reaches m.

Input

First line contains t, number of test cases.

Each test case starts with n (side length of grid), k (growth threshold) and m (final population).

Next n lines contain an nxn grid of integers, where ith row, jth column has an integer representing the number of bacteria present initially at cell (i, j).

1< n <= 100, 0 < k <= 2^45, 0 < m <= 2^45.

There are no more than n cells with initial population equal to or greater than k.

Output

For each test case print the number of seconds required for the total bacteria population to reach m. If m can never be reached print "Not possible" (quotes for clarity).

Example

Input:
1
3 5 15
0 0 0
0 3 0
0 0 5

Output:
3