[ICPC 2022 Xi'an R] Clone Ranran

Luogu
IDLGP9360
Time1000ms
Memory512MB
DifficultyP2
2022O2优化ICPC西安
Ranran needs to prepare a contest! A contest is made of $c$ problems, and Ranran can do one of the following two things: - Clone himself in $a$ minutes. That is, after $a$ minutes, there will be one more Ranran. - Prepare a problem in $b$ minutes. That is, after $b$ minutes, there will be one more problem. Note that a cloned Ranran can also do the two things above. A Ranran cannot do the two things at the same time. Ranran wants to prepare the contest as fast as possible. But he is very lazy, so he asks you to find the minimum number of minutes to prepare the contest. You need to answer $T$ queries independently. ## Input The first line contains an integer $T$ ($1\leq T\leq 10 ^ 5$). Each of the next $T$ lines contains three integers $a$, $b$ and $c$ ($1\leq a, b, c\leq 10 ^ 9$), representing a query. ## Output For each test case, output a line with a single integer representing the answer. [samples] ## Note **Source**: The 2022 ICPC Asia Xi'an Regional Contest Problem C. **Author**: MagicSpark.
Samples
Input #1
5
1 1 1
2 3 3
9 9 9
3 26 47
1064 822 1048576
Output #1
1
7
45
44
21860
API Response (JSON)
{
  "problem": {
    "name": "[ICPC 2022 Xi'an R] Clone Ranran",
    "description": {
      "content": "Ranran needs to prepare a contest! A contest is made of $c$ problems, and Ranran can do one of the following two things: - Clone himself in $a$ minutes. That is, after $a$ minutes, there will be one ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9360"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Ranran needs to prepare a contest! A contest is made of $c$ problems, and Ranran can do one of the following two things:\n\n- Clone himself in $a$ minutes. That is, after $a$ minutes, there will be one ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments