Description

计算行列式.

Input

每组数据由一个整数n(n<=7)开头,后跟n*n个整数(每个整数值<=9),表示一个n阶行列式,若n为0,则输入结束.

Output

对于每个行列式输出一个行列式的值.每个结果占一行.

Sample

Input

3
5 7 1
6 2 3
1 8 4
0

Output

-181

Hint

用64位整型(long long int)数来进行计算,就可以保证n个数的乘积之正确性. 例如:long long int a=1234567891010; cout<<a; 或者:__int64 a=1234567891010; printf("%I64d",a);

Source: 浙工大2008C++期终考试