Beauty of AP
Solving problems is fun in competitive programming, right? So let’s solve a fun task today too :P.
16th December, the day of victory, a memorable day for our nation. You have planned to celebrate the day with some of your friends by inviting them to your home. Well, the nice initiative! But the number of friends to invite not fixed yet. After a while, a peculiar idea comes into your mind.
You take a piece of paper and a pencil and started to write an Arithmetic Progression (AP). The first term of this progression is a and the common difference between every two adjacent terms is d. So if we write the n terms of the sequence from left to write and named them as S = s1, s2, s3, …. sn, then the sequence will be, s1 = a, s2 = a + d, s3 = a + 2d, s4 = a + 3d ….. sn = a + (n - 1) d.
You defined a prefix of length L (1 ≤ L ≤ n) (first L consecutive numbers) of this AP as good if the following conditions hold
- If L = 1 or,
- for every pair of i, j where **1≤_i, j_ ≤L**, if **i !=j** then **(si % L != sj % L)**.
You always want to invite your friends in such a way that if you invite k of your friends then the prefix of length k of the aforementioned AP has to be good.
Count in how many ways you can invite your friends.
You have to Count this for several cases.
Input
First-line will contain a number T, denoting the number of test cases.
Every successive case will contain three numbers a, d and n, where a is the first term of the AP,
d is the common difference and n is the number of terms in the AP.
Constraints:
1 <= T <= 2000
1 ≤ a, n ≤ 1018
1 ≤ d ≤ 1012
Output
In every test case, print a single integer, the number of ways to invite friends . Don’t forget to print a new line after every test case.
Sample
| Input | Output |
|---|---|
1 3 2 5 | 3 |
Explanation: For L = 1, S = (3 % 1 = 0) = (0). For L = 2, S = (3 % 2 = 1, 5 % 2 = 1) = (1, 1). For L = 3, S = (3 % 3 = 0, 5 % 3 = 2, 7 % 3 = 1) = (0, 2, 1) For L = 4, S = (3 % 4 = 3, 5 % 4 = 1, 7 % 4 = 3, 9 % 4 = 1) = (3, 1, 3, 1). For L = 5, S = (3 % 5 = 3, 5 % 5 = 0, 7 % 5 = 2, 9 % 5 = 4, 11 % 5 = 1) = (3, 0, 2, 4, 1). So for L = 1, 3 and 5 we get the desired output. So the answer is 3. | |
Note
Data set is huge, use faster input output.
