2024는 무엇이 특별할까?

• a의 약수들을 d1,d2,…,dl 라고 하자.
• a가 홀수라면 d1,d2,…,dl는 모두 홀수이다.
• 2^m*a의 약수는 di들과 2*di,2^2*di,2^3*di,…,2^m*di 들이다. di들만 홀수이고 나머지는 모두 짝수이므로, 짝수인 약수의 개수는 홀수인 약수의 개수의 m배가 된다
• 따라서, K-특별한수의 개수는 2^k*{홀수} 형태의 수의 개수와 동일하다. N이하의 2^k*{홀수} 형태의 수의 개수는 2^k의 배수의 개수에서 2^(k+1)의 배수의 개수를 빼는 방식으로 구할 수 있다. 시간복잡도는 O(1)

"""Solution code for "BOJ 31247. 2024는 무엇이 특별할까?".

- Problem link: https://www.acmicpc.net/problem/31247
- Solution link: http://www.teferi.net/ps/problems/boj/31247

Tags: [math]
"""

import sys


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        N, K = [int(x) for x in sys.stdin.readline().split()]
        print((N >> K) - (N >> (K + 1)))


if __name__ == '__main__':
    main()