在太平洋的一片海域,发现了大量的油田!
为了方便开采这些能源,人们将这些油田从1到n进行编号,
人们在开采这些油田时,有三种开采方式,分别为方式A,方式B,方式C。
用不同的方式去开采这些油田所消耗的资金不同,为了防止共振导致的油井坍塌,相邻编号的油田不能使用同一种开采方式。
我们希望你求出开采这n个油田所需要消耗的最小资金,并输出开采每个油田所采用的方式。
先输入一个整数T(0 < T <= 100),代表有T组测试数据。对于每组数据,第一行输入一个正整数n(n<1000)代表油田数目,
接下来n行,每一行包含三个整数。第i(2 <= i <= n+1)行的这三个数代表着开采编号为i-1的油田分别采用A,B,C三种方式开采所消耗的资金。
对于每一组测试样本,先输出样本编号,接下来输出一个整数,代表着开采这n个油田所需要消耗的最小资金,然后按编号从小到大的顺序输出开采每个油田所采用的方式。每一组测试样本的输出占一行。
1 2 4 8 3 2 1 4
Case 1: 4 CB
声声醉如兰