Ayan is a small kid loves to play with stars * and dots . and builds different triangles. Today he builds a triangular shape as follows and named it Triangle_Level0.

    ****
    *.*
    **
    *

By placing two Triangle_Level0(s) side by side and one Triangle_Level0 below them, he builds a new structure (in figure 1.1). Then gaps are filled with dots .. Then he names the structure as Triangle_Level1 (in figure 1.2). And similarly, we can also construct Triangle_level2.

 ********
 *.* *.*
 **  **
 *   *
 ****
 *.*
 **
 *

 ********
 *.*.*.*
 **..**
 *...*
 ****
 *.*
 **
 *

 **************** 
 *.*.*.*.*.*.*.*
 **..**..**..**
 *...*...*...*
 ****....****
 *.*.....*.*
 **......**
 *.......*
 ********
 *.*.*.*
 **..**
 *...*
 ****
 *.*
 **
 *

He repeated the same procedure until he built the Triangle_LevelN. Now he wants to know how many stars are in the K^th row after building Triangle_LevelN.

For example, if N = 2, then after building Triangle_Level2, 1^st row (counting of rows starts from the bottom) has 1 star, 2^nd and 3^rd row has 2 stars each, 4^th row has 4 stars, 5^th row has 2 stars, and so on.

Input starts with an integer T (1 ≤ T ≤ 100000) denoting the number of test cases. Each of the test cases will contain two numbers K (1 ≤ K ≤ 10¹⁶) and N (0 ≤ N ≤ 50).

The output should be in the format Case t: x where t is the case number and x is the number of stars. If there is no such row in the triangle of level N, then print -1 instead.