Chef and Bulb Invention solution codechef

Chef and Bulb Invention solution codechef


Chef is trying to invent the light bulb that can run at room temperature without electricity. So he has NN gases numbered from 00 to N1N−1 that he can use and he doesn’t know which one of the NN gases will work but we do know it.

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 KK and selects all indices ii in increasing order such that imodK=0imodK=0 and test the gases on such indices, then all indices ii in increasing order such that imodK=1imodK=1, and test the gases on such indices, and so on.

Given NN, the index of the gas pp that will work, and KK, find after how much time will he be able to give Chefland a new invention assuming that testing 11 gas takes 11 day.

For example, consider N=5,p=2N=5,p=2 and K=3K=3.

  • On the 1st1st day, Chef tests gas numbered 00 because 0mod3=00mod3=0.
  • On the 2nd2nd day, Chef tests gas numbered 33 because 3mod3=03mod3=0.
  • On the 3rd3rd day, Chef tests gas numbered 11 because 1mod3=11mod3=1.
  • On the 4th4th day, Chef tests gas numbered 44 because 4mod3=14mod3=1.
  • On the 5th5th day, Chef tests gas numbered 22 because 2mod3=22mod3=2.

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

Input Format

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first and only line of each test case contains three space-separated integers NNpp, and KK.

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 11 gas takes 11 day.

Constraints

  • 1T1051≤T≤105
  • 1N,K1091≤N,K≤109
  • 0p<N0≤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 11: On the day 11 Chef will test gas numbered 00 and on the day 22 Chef will test gas numbered 55.

Test case 22: On the day 11 Chef will test gas numbered 00, on the day 22 Chef will test gas numbered 55, on the day 33 Chef will test gas numbered 11, and on the day 44 Chef will test gas numbered 66.

Test case 33: On the day 11 Chef will test gas numbered 00, on the day 22 Chef will test gas numbered 55, on the day 33 Chef will test gas numbered 11, on the day 44 Chef will test gas numbered 66, on the day 55 Chef will test gas numbered 22, on the day 66 Chef will test gas numbered 77, on the day 77 Chef will test gas numbered 33, on the day 88 Chef will test gas numbered 88, and on the day 99 Chef will test gas numbered 44.

Test case 44: On the day 11 Chef will test gas numbered 00, on the day 22 Chef will test gas numbered 55, on the day 33 Chef will test gas numbered 11, on the day 44 Chef will test gas numbered 66, on the day 55 Chef will test gas numbered 22, on the day 66 Chef will test gas numbered 77, on the day 77 Chef will test gas numbered 33, and on the day 88 Chef will test gas numbered 88.

Solution: Click here

Leave a Comment