Background

qq820186690的强势回归

Description

奶牛时代里，农历新年马上就要到了，奶牛们（Bill_Yang,ZKX2019,Achen）计划举办一次聚会庆祝新年的到来。但是，奶牛们并不喜欢走太远的路，这会给他们的聚会带来消极情绪，当一头奶牛的消极指数为 w[i]他参加聚会所需行走的距离为 s[i]那么他就会给聚会带来\(s[i]^3*w[i]\)

的消极情绪。所有奶牛所在位置都在一条直线上，已知所有奶牛的坐标和消极指数，求如何确定聚会地点，使得所有奶牛给聚会带来的消极情绪之和最小，输出消极情绪之和的最小值。

Format

Input

第一行包含一个整数 Ca ( Ca ≤ 20 ) ，表示有 Ca 组测试数据，对于每组测试数据：
第一行包含一个整数 n ( 1 ≤ n ≤ 50000 ) ，表示奶牛的数量。
接下来 n 行每行包含两个浮点数x[i] and wi

Output

对于每组测试数据，输出 "Case #c: ans" ，其中 c 表示测试数据编号， ans 表示消极情绪之和的最小值，结果四舍五入为一个整数。

Sample 1

Input

1
5
0.9 2
1.4 4
3.1 1
6.2 1
8.3 2

Output

Case #1: 300

Limitation

1.5s, 262144KiB for each test case.

Source

Bashu Original