LCM - The Time of Day

no tags 

There are no days and nights on byte island, so the residents here can hardly determine the length of a single day. Fortunately, they have invented a clock with several pointers. They have N pointers which can move round the clock. Every pointer ticks per second, and the i-th pointer move to the start position after i times of ticks. The wise of the byte island decide to define a day as the time interval between the start time and the first time when all the pointers moves to the position exactly the same as the start time. The wise of the island decide to choose some of the N pointers to make the length of the day are greater than or equal to a given seconds M. They want to know how many different ways to make it possible.

Input

There are a lot of test cases, the number of test cases are in the first line of input.

For each test cases, there are only one line contains two integers N and M, indicating the number of pointers and the lower bound for seconds of a day. (1 <= N <= 40, 1 <= M <= 263-1)

Output

For each test case, output a single integer denoting the number of ways.

Example

Input:
3
5 5
10 1
10 128

Output:
Case #1: 22
Case #2: 1023
Case #3: 586

hide comments
Francis: 2014-05-06 11:56:27

AC in 1.25s with help from @leppy. I do not know how to optimize my code. Any advice about this prob is welcome for me. If you need to check my code, just let me know,I will give you the link. Thx so much! :)

Last edit: 2014-05-12 08:10:32
Ashish Lavania: 2012-12-29 21:47:19

nice precomputation problem! costed 3 WA but this is my first solved problem added by xilinx


Added by:Fudan University Problem Setters
Date:2011-09-08
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ACM/ICPC Regionals, Shanghai 2011 Preliminary, by g201513