It's a Mod, Mod, Mod, Mod World

시간 제한5초메모리 제한512 MB

요약

p, q, n이 주어질 때 i=1부터 n까지 (p*i mod q)의 합을 구하며, 최대 10^5개의 질의와 10^6 이하의 값이 들어온다.

난이도: 어려움10점 중 8점
유형: 수학, 정수론, 분할 정복, 이분 탐색
정답자: 아직 제출이 없습니다

문제

정수 p, q, n이 주어지는 문제가 여러 개 있다. 이때 (\displaystyle\sum_{i=1}^{n}{((p \cdot i) \text{ mod } q)})를 구한다. 즉, p의 처음 n개 배수를 q로 나눈 나머지의 합을 구한다. 전체 합에는 모듈러 연산을 적용하지 않는다.

입력

입력의 첫 줄에는 해결해야 할 케이스의 수 W (1 ≤ W ≤ 10^5)가 주어진다.

다음 W개 줄에는 각각 p, q, n (1 ≤ p, q, n ≤ 10^6)이 공백으로 구분되어 주어진다. 이는 위에서 설명한 문제의 매개변수이다.

출력

입력에 나타난 순서대로 각 인스턴스의 답을 한 줄에 하나씩 W개 줄에 출력한다.

예제1

예제 1
입력
```
3
2 7 2
1 4 5
3 8 10
```
예상 출력
```
6
7
37
```