往届 ACM 队训练题 (参考)

1046. 数塔IV

单点时限: 2.0 sec

内存限制: 256 MB

有一个由正整数组成的三角形,第一行只有一个数,除了最下行之外每个数的左下方和右下方各有一个数,如下图所示。

1

3 2

4 10 1

4 3 2 20

从第一行的数开始,每次都只能左下或右下走一格,直到走到最下行,把沿途经过的数全部乘起来。如何走,使得个位数的积尽量大 ?

输入格式

输入数据首先包括一个整数 C, 表示测试实例的个数,每个测试实例的第一行是一个整数 N(1 <= N <= 100),表示数塔的高度,接下来用 N 行数字表示数塔,其中第 i 行有个 i 个整数,且所有的整数均在区间 [0,99] 内。

输出格式

对于每个测试实例,输出可能得到的最大个位数。

样例

Input
1
4
1
3 2
4 10 1
4 3 2 20
Output
8
不限期开放

题目列表