#Code Written by : John Nixon
#Date: 06:08:2022  Time: 14:20:19
#Copyrights are applicable
import sys
import os
sys.setrecursionlimit(10000)
try:
    sys.stdin = open('./input.txt', 'r')
    sys.stdout = open('./output.txt', 'w')
except:
    pass

# 1
# 11
# 78 97 23 6 51 52 28 60 33 1

bits = {}
bits[0] = 0
bits[1] = 1
bits[2] = 1
def count_set_bits(n):
    if n in bits:
        return bits[n]
    # base case
    if (n == 0):
        return 0
    else:
        bits[n] = 1 + count_set_bits(n & (n - 1))
        return bits[n]

def Z_seq(P,Q,N):
    numbers = [2]

    for i in range(1,N):
        Z = P * count_set_bits(numbers[-1]) + Q
        if Z in numbers:
            idx = numbers.index(Z)
            break
        else:
            numbers.append(Z)

    val = N  % len(numbers) - i
    return count_set_bits(numbers[val])

T = int(input())

for _ in range(T):
    P,Q,N = map(int,input().split())

    out_ = Z_seq(P,Q,N)
    print(out_)