弹吉他

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

百小度立志在大学期间学会一门乐器,果不其然他买了一把吉他。

我们知道,弹吉他需要用左手手指在琴柄上按出各种和弦。通常情况下一首曲子需要按好多个和弦,下图就是C和弦的一种指法:


吉他谱里面,我们用1至4分别表示食指、中指、无名指、小拇指,上面表示食指按在2弦1品,中指按在4弦2品,无名指按在5弦3品。

而百小度现在正在挑战一首非常难的曲子,曲子里有 n 个和弦,而且每个和弦都需要用到四根手指头。转换和弦过程中,拇指每移动一根弦或者移动一品,都会消耗一点能量。百小度想知道,弹完这首曲子所需的能量总和最少是多少。

假定最开始左手的四根手指头依次位于“0弦”的1品到4品,“0弦”是虚拟的,表示手指头现在不按着任何弦。我们还考虑到这么一个问题,如果食指按在3品,那么中指不可能按在1品,也就是说序号大的手指所处的品位不能小于序号小的手指。


Input

第一行一个整数T,表示T组数据。

每组数据第一行一个正整数 n ,表示和弦数量。接下去 n 行,每行包含第4对不同的 a 、 b ,表示 a 弦 b 品。

数据范围
$1 \leq n \leq 5000$
$1 \leq a \leq 6$
$1 \leq b \leq 4$

Output

对于每组测试数据,先输出一行

Case #i:

然后输出一个整数,表示最小能量。

Sample Input

2 1 1 1 2 1 3 1 4 1 2 1 1 2 2 4 3 6 4 1 3 4 3 6 3 1 4

Sample Output

Case #1: 16 Case #2: 25

Hint

hujie

Source

2015年百度之星程序设计大赛 - 复赛

提交代码