可恶的魔鬼，设置了令人沮丧的迷宫，阻隔了我和TA相会的路.
我一次次尝试，却一次次被送出迷宫.
虽然到现在为止还是没有成功，但是，我依旧发现了迷宫的一些秘密.
我终于明白，我面对的是一个完全动态的迷宫.
我到了一个房间，我必须仔细选择下一步往哪里去.
上/下/左/右？我不知道
即便如此，我依旧通过我与生俱来的感知能力察觉到了每个房间把我传送出去的概率.
我最后一次站在入口，我要与TA一起，离开魔鬼的掌控.
我相信我能选出最好的路线.
神，请告诉我，我们有多大概率能够相会？
（注：若被传送出迷宫，则本次尝试不能相会.）
单组测试，第一行一个整数n<=100，表示迷宫的大小，我在左上角即(0, 0)，TA在右下角即(n-1, n-1).
接下来n行，每行n个浮点数，表示该点把我传送出去的概率，输入保证所有浮点数精确到小数点后一位.
我和TA的位置保证为0.0
如果我们不可能再相见，请输出"QAQ~"，不包含引号.
否则，输出概率值，保留到小数点后6位.
4
0.0 0.0 0.0 0.0
0.0 0.0 0.0 0.0
0.0 0.0 0.0 0.0
0.0 0.0 0.0 0.0
1.000000