You are playing a very popular game called Cubecraft. Initially, you have one stick and want to craft $k$ torches. One torch can be crafted using one stick and one coal.

Hopefully, you've met a very handsome wandering trader who has two trade offers:  exchange $1$ stick for $x$ sticks (you lose $1$ stick and gain $x$ sticks).  exchange $y$ sticks for $1$ coal (you lose $y$ sticks and gain $1$ coal). 

During one trade, you can use only one of these two trade offers. You can use each trade offer any number of times you want to, in any order.

Your task is to find the minimum number of trades you need to craft at least $k$ torches. The answer always exists under the given constraints.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow.

The only line of the test case contains three integers $x$, $y$ and $k$ ($2 \le x \le 10^9$; $1 \le y, k \le 10^9$) — the number of sticks you can buy with one stick, the number of sticks required to buy one coal and the number of torches you need, respectively.


-----Output-----

For each test case, print the answer: the minimum number of trades you need to craft at least $k$ torches. The answer always exists under the given constraints.


-----Example-----
Input
5
2 1 5
42 13 24
12 11 12
1000000000 1000000000 1000000000
2 1000000000 1000000000

Output
14
33
25
2000000003
1000000001999999999

Difficulty: interview

Starter code:

Solutions:
for haaghfj in range(int(input())):
    x,y,k = list(map(int,input().split()))
    print(k + (y * k + k - 1 +x-2) // (x - 1))


import sys
import math
import collections
import bisect
import itertools
import decimal
import copy
import heapq

# import numpy as np

# sys.setrecursionlimit(10 ** 6)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list([int(x) - 1 for x in sys.stdin.readline().rstrip().split()])
flush = lambda: sys.stdout.flush()


# ===CODE===
def main():
    t = ni()

    for _ in range(t):
        x, y, k = ns()
        ans = k
        total = k + k * y - 1

        ans += -(-total // (x - 1))
        print(ans)


def __starting_point():
    main()

__starting_point()

for _ in range(int(input())):
    x, y, k = [int(s) for s in input().split()]
    n = ((y + 1) * k - 1 + (x - 2)) // (x - 1)
    print(n + k)


q = int(input())
for t in range(q):
    x, y, k = list(map(int, input().split()))
    a = ((y + 1) * k - 1 + x - 1 - 1) // (x - 1)
    b = k
    print(a + b)


t = int(input())

for i in range(t):
    x, y, k = list(map(int, input().split()))

    a = (y + 1) * k - 1

    # print(a)

    print((a - 1) // (x - 1) + 1 + k)


from collections import defaultdict
from queue import deque


def arrinp():
    return [*list(map(int, input().split(' ')))]


def mulinp():
    return list(map(int, input().split(' ')))


def intinp():
    return int(input())


def solution():
    x,y,k = mulinp()
    num = y*k + k
    ans = (num-1)//(x-1)
    if (num-1)%(x-1) != 0:
        ans += 1
    ans += k
    print(ans)


testcases = 1
testcases = int(input())
for _ in range(testcases):
    solution()


t=int(input())
for i in range(t):
    z=list(map(int, input().split()))
    x=z[0]
    y=z[1]
    k=z[2]
    palok=k*y+k-1
    ans=0
    ans=palok//(x-1)
    if palok%(x-1)!=0:
        ans+=1
    print(ans+k)


tests = int(input())
for test in range(tests):
    a = 1
    x, y, k = list(map(int, input().split()))
    a1 = (k * (y + 1) - 1 + x - 2) // (x - 1)
    print(a1 + k)


t = int(input())
for _ in range(t):
    x, y, k = map(int, input().split())
    n = (k * (y + 1) - 1 + (x - 2)) // (x - 1)
    print(n + k)

for _ in range(int(input())):
    x, y, k = map(int, input().split())

    print((k*y+k-1+x-2)//(x-1)+k)

from math import ceil


def read_int():
    return int(input())


def read_ints():
    return list(map(int, input().split(' ')))


t = read_int()
for case_num in range(t):
    x, y, k = read_ints()
    a = (k * (y + 1) - 2) // (x - 1) + 1 + k
    print(a)


import sys
input = sys.stdin.readline

for _ in range(int(input())):
    x, y, k = [int(i) for i in input().split()]
    
    stick_need = k+k*y-1
    
    num_stick_trade = (stick_need+x-2)//(x-1)

    
    print(num_stick_trade+k)

for _ in range(int(input())):
	x,y,k=map(int,input().split()) 
	a=(y+1)*k-1 
	b=x-1 
	if a%b==0:
		c=a//b
	else:
		c=a//b+1 
	print(c+k)

import sys

sys.setrecursionlimit(10**5)
int1 = lambda x: int(x)-1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

for _ in range(II()):
    x,y,k=MI()
    a=(k*(y+1)-1+x-2)//(x-1)
    print(a+k)


import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return list(map(int, minp().split()))

def solve():
	x, y, k = mints()
	ta = k*(y+1)
	d = ((ta-1)+(x-2))//(x-1)
	print(d+k)

for i in range(mint()):
	solve()


#!/usr/bin/env python3
import sys
input = sys.stdin.readline

t = int(input())
for i in range(t):
    x, y, k = map(int, input().split())
    needed = k + y * k
    trades = ((needed - 1) + (x - 2)) // (x - 1)
    trades += k
    print(trades)

t = int(input())

for ii in range(t):

	x, y, k = map(int, input().split())

	coals = k
	sticks = k

	sticks = k*y + k

	num = (sticks-1)//(x-1)

	if (sticks-1)%(x-1) != 0:
		num+=1

	num += k

	print(num)