Iterated Bitcount Function

Let f(x) be the number of 1's in the binary representation of x. We can define f^k(x) as f(x) for k = 1, and f^(k-1)(f(x)) for k > 1. Let f^*(x) be the smallest k >= 1 such that f^k(x)=1. Given N and K, how many numbers x between 1 and N inclusive have f^*(x) = K ? Input The first line contains the number of test cases T. Each of the next T lines contains two space separated numbers N and K. O