There are two infinite sources of water:  hot water of temperature $h$;  cold water of temperature $c$ ($c < h$). 

You perform the following procedure of alternating moves:  take one cup of the hot water and pour it into an infinitely deep barrel;  take one cup of the cold water and pour it into an infinitely deep barrel;  take one cup of the hot water $\dots$  and so on $\dots$ 

Note that you always start with the cup of hot water.

The barrel is initially empty. You have to pour at least one cup into the barrel. The water temperature in the barrel is an average of the temperatures of the poured cups.

You want to achieve a temperature as close as possible to $t$. So if the temperature in the barrel is $t_b$, then the absolute difference of $t_b$ and $t$ ($|t_b - t|$) should be as small as possible.

How many cups should you pour into the barrel, so that the temperature in it is as close as possible to $t$? If there are multiple answers with the minimum absolute difference, then print the smallest of them.


-----Input-----

The first line contains a single integer $T$ ($1 \le T \le 3 \cdot 10^4$) — the number of testcases.

Each of the next $T$ lines contains three integers $h$, $c$ and $t$ ($1 \le c < h \le 10^6$; $c \le t \le h$) — the temperature of the hot water, the temperature of the cold water and the desired temperature in the barrel.


-----Output-----

For each testcase print a single positive integer — the minimum number of cups required to be poured into the barrel to achieve the closest temperature to $t$.


-----Example-----
Input
3
30 10 20
41 15 30
18 13 18

Output
2
7
1



-----Note-----

In the first testcase the temperature after $2$ poured cups: $1$ hot and $1$ cold is exactly $20$. So that is the closest we can achieve.

In the second testcase the temperature after $7$ poured cups: $4$ hot and $3$ cold is about $29.857$. Pouring more water won't get us closer to $t$ than that.

In the third testcase the temperature after $1$ poured cup: $1$ hot is $18$. That's exactly equal to $t$.

Difficulty: interview

Starter code:

Solutions:
import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    h, c, t = list(map(int, input().split()))
    if h + c >= 2 * t:
        print(2)
    else:
        diff2 = 2*t - (h + c)
        hDiff2 = 2*h - (h + c)

        kDown = (hDiff2//diff2 - 1)//2
        kUp = kDown + 1
        diffDown = abs(diff2 - hDiff2/(2 * kDown + 1))
        diffUp = abs(diff2 - hDiff2/(2 * kUp + 1))
        if diffDown <= diffUp:
            print(2 * kDown + 1)
        else:
            print(2 * kDown + 3)


from fractions import Fraction as F

def solve():
    h, c, t = map(int, input().split())
    dt = abs(F(h - t))
    ans = 1
    def update(u, v):
        nonlocal dt, ans
        if u <= 0 or v < 0:
            return
        w = F(u * h + v * c, u + v)
        if abs(w - t) < dt:
            dt = abs(w - t)
            ans = u + v
    update(1, 1)
    ax = (h - t) // (2 * t - h - c) if 2 * t - h - c else 0
    for x in range(ax - 3, ax + 4):
        update(x + 1, x)
    print(ans)

t = int(input())
for _ in range(t):
    solve()

from sys import stdin
input = stdin.readline
q = int(input())
for _ in range(q):
	h,c,t = map(int,input().split())
	if 2*t <= h+c:
		print(2)
	else:
		t*=2
		h*=2
		c*=2
		w = h//2-c//2
		pod = (h+c)//2
		#w/(2k+1) jak najblizej t-pod
		goal = t-pod
		if goal == 0:
			print(1)
		else:
			x = w//goal
			wynik = 2
			mini = 23649823847238
			for szkl in range(x-3,x+4):
				if szkl%2 == 1 and szkl >= 1 and abs(goal-w/szkl) < mini:
					mini = abs(goal-w/szkl)
					wynik = szkl
			print(wynik)

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


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


tt = read_int()
for case_num in range(tt):
    h, c, t = read_ints()
    if 2 * t <= h + c:
        print(2)
        continue
    l = 1
    r = int(1e7)

    def calc(x): return x * h + (x - 1) * c
    while l <= r:
        mid = (l + r) // 2
        temp = calc(mid)
        if temp >= t * (2 * mid - 1):
            l = mid + 1
        else:
            r = mid - 1
    a = calc(l - 1)
    b = calc(l)
    p = 2 * l - 3
    q = 2 * l - 1
    if abs(a * q - t * p * q) <= abs(b * p - t * p * q):
        print(p)
    else:
        print(q)


t = int(input())

for _ in range(t):
    h, c, g = [int(x) for x in input().split()]
    av = (h + c)/2
    if g == h:
        print(1)
    elif g <= av + 0.001:
        print(2)
    else:
        # after 2n+1 pours (n = 0, 1, ...) we have a temp of ((n+1)*h + n*c)/(2*n+1) = g,
        # so we have n*(h+c) + h = g*(2*n+1),
        # or n*(h+c) + h = g*2*n + g
        # or n*(h+c-g*2) = g - h
        # or n ~= (g-h)/(h+c-g*2)
        n = int((g-h)/(h+c-g*2))
        best_n = -1
        for j in range(max(n-3, 0), n+3):
            if best_n == -1 or \
                    abs(((best_n + 1)*h + best_n*c) - (2*best_n+1)*g)*(2*j+1) > \
                    abs(((j + 1)*h + j*c) - g*(2*j+1))*(2*best_n+1):
                best_n = j
        print(2*best_n+1)


import sys

input = sys.stdin.readline
flush = sys.stdout.flush

for _ in range(int(input())):
    h, c, t = list(map(int, input().split()))
    m = h + c >> 1
    if t <= m:
        print(2)
        continue
    a = (h - t) // (2*t - h - c)
    b = a + 1
    print(2*a + 1 if 2*t*(2*a+1)*(2*b+1) >= (2*b+1)*((a+1)*h+a*c)+(2*a+1)*((b+1)*h+b*c) else 2 * b + 1)


T = int(input())
for _ in range(T):
    h, c, t = list(map(int, input().split()))
    if h + c >= t * 2:
        print(2)
    else:
        l, r = 0, 10 ** 9
        while r - l > 1:
            m = (l + r) // 2
            if h * (m + 1) + c * m >= t * (2 * m + 1):
                l = m
            else:
                r = m
        if (2 * l + 1) * ((2 * r + 1) * t - (h * (r + 1) + c * r)) >= (2 * r + 1) * (h * (l + 1) + c * l - (2 * l + 1) * t):
            print(l * 2 + 1)
        else:
            print(r * 2 + 1)


from fractions import Fraction

T = int(input())


def TMP(h, c, nbH):
    return c + Fraction(nbH, 2*nbH-1) * (h-c)


for _ in range(T):
    h, c, t = [int(_) for _ in input().split()]
    if t <= (h+c)//2:
        print(2)
        continue
    L, R = 1, 10**9
    a = 0
    while L <= R:
        m = (L+R)//2
        tmp = TMP(h, c, m)
        if tmp >= t:
            L = m+1
            a = m
        else:
            R = m-1
    b = a+1
    if abs(TMP(h, c, a) - t) <= abs(TMP(h, c, b) - t):
        print(a*2-1)
    else:
        print(b*2-1)


from fractions import Fraction
from math import ceil, floor

for _ in range(int(input())):
    h, c, t = list(map(int, input().split()))
    if t * 2 <= h + c:
        print(2)
    else:
        # (t - (h + c) / 2) ~~ ((h - c) / 2) / ans
        c1 = t - Fraction(h + c, 2)
        c2 = Fraction(h - c, 2)
        goal = c2 / c1
        goal1 = (goal + 1) / 2
        ans1 = floor(goal1) * 2 - 1
        ans2 = ceil(goal1) * 2 - 1
        if c2 / ans1 + c2 / ans2 <= c1 * 2:
            print(ans1)
        else:
            print(ans2)