# 4971 子树的大小
# n ×树的左右节点公式
# l = point * n - n + 2
# r = point * n + 1
T = int(input())

ans = []

def deal(n, m, k):
    l, r = k, k
    res = 1
    an = 1
    while(n >= m * r + 1):
        res = res * m
        an += res
        l = m * l - m + 2
        r = m * r + 1
    lef = m * l - m + 2
    an += max(0, n - lef + 1)
    return an

while(T):
    n, m, k = map(int, input().split())
    ans.append(deal(n, m, k))
    T -= 1
for i in ans:
    print(i)