第k个1

Time Limit: 1000ms

Memory Limit: 65536K

Description

Shangke7788对数字比较感兴趣,经常玩弄数字间的逻辑关系。
某一天发现了这样一串奇妙的4个连续数字: 5, 6, 7, 8,这四个数字它存在这样一种特殊的关系,我们分别将他们转化成二进制数,5(101),6(110),7(111),8(1000),其中5的第一位是1,6的第二位是1,7的第三位是1,8的第四位是1,而下一个数字9(1001),的第5位不是1,因此不能归于这组序列中。于是他就把这种数串定义为shangke数列,以下给出shangke数列的定义:
(1) 这个数列都是有限数列,所有数字都是自然数.
(2) 数列后一个数字永远比前一个数字大1.
(3) 数列中第1个数二进制的第1位(最低位)是1,第2个数二进制的第2位(次低位)是1,依次类推,假设数列共有n个元素,那么对于任意的1<=k<=n,ak表示第k个数,那么ak的二进制的第k位必须是1。
符合上述3个条件的数列称为shangke数列.
shangke数列的大小以最小的数字作为其大小的象征,元素个数不同的2个shangke数列不能比较大小。

Input

第一行输入一个整数T, 表示有T组测试数据。
每组Case,输入两个整数n(1<=n<=10^18), k(1<=k<=10^18),表示第k大的含有n个数字的shangke数列。

Output

输出以Case X: N的形式,X是当前的Case数目,从1开始计数,N为当前Case的shangke数列最小的数字 MOD (10^9+9)的值

Sample Input

2
2 1
4 1

Sample Output

Case 1: 1
Case 2: 5

Hint

None

Source

Shangke7788

提交代码