You are given multiple problems with three integers , , and . Find . That is, the first multiples of , modulo , summed. Note that the overall sum has no modulus.
输入格式
Each input will begin with a line with a single integer (), which is the number of cases you must solve.
Each of the next lines will contain three space-separated integers , and (), which are the parameters of the problem as described above.
输出格式
Output lines, each with the answer for a given instance of the problem, in the order that they appear in the input.
