Hello coders, today we are going to solve **Chef and Bulb Invention CodeChef Solution** whose Problem Code is **CHFINVNT**.

**Task**

Chef is trying to invent the light bulb that can run at room temperature without electricity. So he has * N* gases numbered from

*to*

**0***that he can use and he doesn’t know which one of the*

**N − 1***gases will work but we do know it.*

**N**Now Chef has worked on multiple search algorithms to optimize search. For this project, he uses a modulo-based search algorithm that he invented himself. So first he chooses an integer * K* and selects all indices

*in increasing order such that*

**i****i mod**and test the gases on such indices, then all indices i in increasing order such that

*K*= 0**i mod**, and test the gases on such indices, and so on.

*K*= 1Given * N*, the index of the gas

**that will work, and**

*p***, find after how much time will he be able to give Chefland a new invention assuming that testing**

*K***1**gas takes

**1**day.

For example, consider ** N = 5**,

**and**

*p*= 2**.**

*K*= 3- On the
**1st**day, Chef tests gas numbered**0**because**0 mod 3 = 0**. - On the
**2nd**day, Chef tests gas numbered**3**because**3 mod 3 = 0**. - On the
**3rd**day, Chef tests gas numbered**1**because**1 mod 3 = 1**. - On the
**4th**day, Chef tests gas numbered**4**because**4 mod 3 = 1**. - On the
**5th**day, Chef tests gas numbered**2**because**2 mod 3 = 2**.

So after **5** days, Chef will be able to give Chefland a new invention

**Input Format**

- The first line of the input contains a single integer
denoting the number of test cases. The description of*T*test cases follows.**T** - The first and only line of each test case contains three space-separated integers
,**N**, and**p**.**K**

**Output Format**

For each test case, print a single line containing one integer — after how much time Chef will be able to give Chefland a new invention assuming that testing **1** gas takes **1 **day.

**Constraints**

**1 ≤***T*≤ 10^5**1 ≤***N*,*K*≤ 10^9**0 ≤***p*<*N*

**Subtasks**

**Subtask #1 (100 points):** Original constraints

**Sample Input 1**

```
4
10 5 5
10 6 5
10 4 5
10 8 5
```

**Sample Output 1**

```
2
4
9
8
```

**Explanation**

Test case 1: On the day **1** Chef will test gas numbered **0** and on the day **2** Chef will test gas numbered **5**.

**Test case 2:** On the day **1** Chef will test gas numbered **0**, on the day **2** Chef will test gas numbered **5**, on the day **3** Chef will test gas numbered** 1**, and on the day **4** Chef will test gas numbered **6**.

**Test case 3:** On the day** 1** Chef will test gas numbered **0**, on the day **2** Chef will test gas numbered **5**, on the day **3** Chef will test gas numbered** 1**, on the day **4** Chef will test gas numbered **6**, on the day **5** Chef will test gas numbered **2**, on the day **6** Chef will test gas numbered **7**, on the day **7** Chef will test gas numbered **3**, on the day **8** Chef will test gas numbered **8**, and on the day **9** Chef will test gas numbered **4**.

**Test case 4:** On the day **1** Chef will test gas numbered **0**, on the day **2** Chef will test gas numbered **5**, on the day **3** Chef will test gas numbered **1**, on the day **4** Chef will test gas numbered **6**, on the day **5** Chef will test gas numbered **2**, on the day **6** Chef will test gas numbered **7**, on the day **7** Chef will test gas numbered **3**, and on the day **8** Chef will test gas numbered **8**.

**Solution – Chef and Bulb Invention**

**C++**

**Python**

T = int(input()) for _ in range(T): n, p, k = map(int, input().split()) ans = 0 a = p%k - 1 b = ((n-1)//k)*k b = n - 1 - b if (a>b): ans += (b+1)*((n-1)//k + 1) +(a-b)*((n-1)//k) else: ans += ((n-1)//k + 1)*(a+1) for i in range(a+1, n, k): ans += 1 if (i==p): print(ans) break

**Java**

**Disclaimer:** The above Problem **(Chef and Bulb Invention) **is generated by **CodeChef** but the Solution is Provided by **CodingBroz**. This tutorial is only for **Educational** and **Learning** Purpose.