小帆帆被困在一个 NxN 的方格矩阵迷宫，每个格子中都有一个整数 A[i][j]。小帆帆从迷宫起点（左上角）格子 A[1][1]开始走，每一步可以向右或向下移动，目标是移动到迷宫的出口右下角 A[N][N]。
小帆帆需要支付的费用包括路径中经过的所有格子中的整数之和，以及改变移动方向需要支付的费用。
小帆帆第一次改变方向的费用是 1，第二次的费用是 2，第三次的费用是
4，…… 第 K 次的费用是2𝑘−1。
请你帮小帆帆算出要离开迷宫的最小花费。第一行一个整数T，代表测试数据组数。
每一组第一行一个整数N。 (1 ≤ N ≤ 100)
以下N行每行N个整数，代表矩阵A。 (1 ≤ A[i][j] ≤ 100)
从起点到终点路径的最小花费。