Description 你打算在某天晚上进行一些神秘的活动，一共打算进行K个活动。

你有n类活动可供选择，对于第i类活动，最多能进行c次，否则可能会出现意外。

另外你有一个晚上需要睡觉的邻居，你的活动可能会吵醒她，

具体的，对于第i类活动，进行一次活动之后她有a/b；的概率是醒着的，否则她是睡着的。

因此你需要安排K个活动分别进行的是哪一类，最小化她被吵醒至少一次的概率Q（她被吵醒得之前必须是睡着的）。

她一开始是醒着的。

n≤10^4，K≤10^6，∑c_i≤10^6，0≤a_i≤b_i≤10^6，1≤b_i,c_i

Input

木题有多组数据。

第一行为数据组数 T 。

接下来有 T 组数据，每组数据第一行有两个正整数n,K。

之后 n 行，每行有三个整数描述一类活动，形如"a_i/b_ic_i"。

Output

对于第 i 组数据，输入一行形如"Case #i:Q",Q即为所求的答案。

答案保留10位小数

Sample Input 3 4 1 1/2 3 1/5 2 2/5 1 2/2 2 3 2 1/2 2 1/3 2 3/4 2 3 3 99/100 1 1/2 2 1/50 3

Sample Output

Case #1: 0.0000000000 Case #2: 0.0833333333 Case #3: 0.0150000000

Data Constraint

对于前10%的数据,n,K<=ll

对于前50%的数据,n,sigma c_i<=200

对于所有数据，T均不会很大，大概不超过30，数据不均为极限数据,

希望大家尽可能优化第法。