import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data: return
    T = int(input_data[0])
    idx = 1
    results = []
    for _ in range(T):
        n = int(input_data[idx])
        k = int(input_data[idx+1])
        idx += 2
        
        if n == 0:
            results.append("0")
            continue
            
        # Số lần gấp đôi tối đa có thể thực hiện
        m = n.bit_length() - 1
        if n % 2 == 0:
            m = min(m, k)
        else:
            m = min(m, k - 1)
            
        q = n // (2**m)
        r = n % (2**m)
        ans = q + bin(r).count('1')
        results.append(str(ans))
    
    sys.stdout.write("\n".join(results) + "\n")

solve()

$\color{#FF2E8A}{♡^♡}
\color{#FF3B94}{𝕻}
\color{#FF4FA3}{𝖍}
\color{#FF61AE}{𝖚}
\color{#FF73B6}{𝖔}
\color{#FF85BF}{𝖓}
\color{#FF97C8}{𝖌}
\color{#FFA9D1}{𝖌} \ 
\color{#FFB9D9}{𝕷}
\color{#FFC9E1}{𝖎}
\color{#FFD6E8}{𝖓}
\color{#FFE3EF}{𝖍}
\color{#FFF0F6}{𝖍}
\color{#FF2E8A}{♡^♡}$