已經沒什麼好害怕了

題目敘述

認識學姊後，Madoka Kaname與Sayaka Miki很好奇魔法少女是什麼身分，這時Kyubey跳了出來，向她們解釋：魔法少女，是以「可以實現任何一個願望」的代價與Kyubey交換契約後，背負著「討伐魔女」此一使命的存在，是十分偉大的身分。「跟我訂下契約，成為魔法少女吧！」Kyubey突然跳出了這一句話，可是她們還沒想到有什麼重要的願望，也不知道魔法少女到底在做什麼，一時無法回答，因此學姊Mami Tomoe決定帶她們實地觀摩一次。回到了一片漆黑的詭異世界，前面突然出現了全身發亮非場醜陋、噁心、以及聚集所有負面形容詞的魔女撲了過來，據Kyubey說法，這東西會帶給附近生活的人極大的厄運。學姊跳了一下 ( 神秘的變身動畫 ) ，變出了一大堆的步槍轟轟轟的就把那怪物打爆了，真的超猛。

在這幾天，Madoka Kaname與Sayaka Miki不斷的崇景魔法少女為民除害的偉大使命。兩人走在路上，突然間感受到了魔女的氣息，可是他們根本毫無能力，因此它們決定趕緊找學姊來幫忙。當他們三個人走入魔女的結界時，另一個腳步聲傳了過來，竟然是那個討厭的轉學生Homura Akemi，「這你打不贏的。」她冷冷地說，但是學姊則以迅雷不及掩耳的速度把她綁了起來，逕自帶著Madoka Kaname與Sayaka Miki向前進。前方只見一個布娃娃坐在一個憑空出現的椅子上，看起來就很弱的樣子，可惡的Homura Akemi根本是在騙他們，學姊Mami Tomoe拿著她自豪的武器，瞄著她的動也不動的布娃娃瘋狂射擊，蹦蹦蹦，無力的布娃娃就被炸爛飛到空中，當一切正要結束時...。

此時Homura Akemi的束縛立刻化為烏有，為了拯救兩位毫無戰鬥力的同學，她必須獨自應戰。Homura Akemi計畫要以一些炸藥炸掉魔女，可是炸藥的份量必須準確拿捏，太少炸不死魔女，太多會波及無辜的人，而且Homura Akemi總是依照炸藥的編號順序投擲炸藥。可是魔女也十分的有抵抗能力，Homura Akemi第$i$顆炸藥爆炸時理論上會造成$i$的傷害，實際上這炸彈碰到魔女時會被分裂為數量最多，且每個裂片傷害皆為$k$的碎片，而由於碎片十分的分散，該枚炸彈對魔女造成的總傷害也衰減為$k$，但由於Homura Akemi的能力很強，分裂的炸彈不會裂到大小變成$1$。比如說Homura Akemi丟出的炸彈編號是$87$，那會分裂成$27$塊傷害為$3$的碎片，造成總傷害為$3$；而編號$89$的炸彈因Homura Akemi的能力而不分裂，維持$89$的傷害。在一旁觀望戰鬥的Madoka Kaname與Sayaka Miki看到Homura Akemi準確地把編號$A$到編號$B$的炸彈炸在魔女身上，雖然十分的震驚與害怕，但也很好奇此時魔女到底承受了多少傷害，在遠方默默關注這一切的你能幫忙計算嗎？

輸入說明

第一行包含一個整數$T$，表示Homura Akemi經歷了幾輪戰鬥。接下來有$T$行，每行包含兩個數字$L,R$，表示在該輪戰鬥中使用了編號$L$到編號$R$的炸彈。保證炸彈都有準確的命中魔女。

保證：

$T \leq 10^5$
$2 \leq L \leq R \leq 4\times 10^7 $

輸出說明

在第$i$輪戰鬥輸出$Case~i:$，標記這是第$i$輪的戰鬥，在下一行輸出其魔女承受的傷害，並換行。

範例輸入

2
2 10
3 7

範例輸出

Case 1:
28
Case 2:
19

提示

第一筆測資中，炸藥造成的傷害分別為$2$,$3$,$2$,$5$,$2$,$7$,$2$,$3$,$2$，總計為$28$的傷害

公告

題目原敘述那會分裂成27塊傷害為3的碎片修正為那會分裂成29塊傷害為3的碎片

Judge Setting

run-time limit: 3000 ms
memory limit: 65536000 byte
測資數量: 0