3007: 七彩原石

有一天，一位彩虹岛的居民制造了一个大新闻，他在深山中发现了一块巨大的七彩原石。这块七彩原石呈长条状，并分成长度不同的许多段，每一段有一种颜色（赤、橙、黄、绿、青、蓝、紫中的一种）。经过专业人士的鉴定，这块原石是上好的建材。彩虹岛的工匠们决定用这块原石建造一座横跨东西的彩虹桥。为了整体的美观性，彩虹桥必须是左右对称的（对称指的是彩虹桥两侧距离中线距离相等的地方颜色必须相同），因此工匠们不会选用整块原石，而是从中截取连续的一部分作为彩虹桥的建材。同时，他们希望这座桥能够尽可能的长。
给出彩虹原石每一段的颜色与长度，请计算彩虹桥的最大长度。

输入第一行为一个整数$T$，表示一共有$T$组数据。
对于每组测试数据：
第一行为一个整数$N(N \leq 2000)$，表示七彩原石共分成$N$段。
接下来有$N$行，第$i$行有$2$个整数$color_{i}$与$length_{i}$，表示七彩原石第$i$ 段的颜色与长度（$1 \leq color_{i} \leq 7$，表示$7$种颜色，$1 \leq length_{i} \leq 10^{9}$）。

对于每组测试数据，输出一个整数$L$表示彩虹桥的最大长度。

2
1
1 1
5
4 1
1 1
2 3
1 2
3 1

1
5