Bob is tired of losing to Alice and, to ensure he doesn't lose again, decided to choose a game in which he is guaranteed to win. Bob has thought of a number from (1) to (n), where it is known that (n = 2^d) for some non-negative integer (d). Initially, Alice knows whether the chosen number is even or not. In one move, Alice can either halve the number or subtract (1). Alice can only halve the number if the current number is even. Only Alice takes turns. After her move, Alice receives a response from Bob: either (-1), which means the number has become (0) and Alice has won, or a non-negative integer (x). If we denote the current number as (a), then for (x) the following conditions hold simultaneously: (a) is divisible by (2^x). (a) is not divisible by (2^{x+1}). For example, if (a=5), then (x=0), since (5) is divisible by (2^0=1) and not divisible by (2^1=2), and if (a=12), then (x=2), since (12) is divisible by (2^2=4) and not divisible by (2^3=8). It can be shown that for any integer (a > 0), there exists a unique such (x). Bob is still afraid that Alice will win, so the game will have no more than (k) moves. Additionally, Bob wants to maximize his chances of winning, so he wants to play as many games as possible. Given (n) and (k), calculate the number of initial numbers from (1) to (n) such that Alice, playing optimally, cannot win in no more than (k) moves. The first line contains an integer (t) ((1 \le t \le 10^4)) — the number of test cases. The only line of each test case contains (2) integers (n) and (k) ((1 \le n, k \le 10^9)) — the limit on the chosen number and the maximum number of Alice's moves, respectively. It is guaranteed that (n = 2^d) for some non-negative integer (d). For each test case, output the number of integers from (1) to (n) such that Alice, playing optimally, can