만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

단순한 문제 (Large)

시간 제한2.4초메모리 제한1024 MB

요약
x, y, z를 각각 a, b, c 이하의 양의 정수로 골라 x mod y, y mod z, z mod x가 모두 같은 경우의 수를 셉니다. 질의는 최대 600,000개입니다.
난이도

어려움10점 중 9점

유형
정수론, 수학, 완전 탐색
정답자
아직 제출이 없습니다

문제

시간 제한 2400 ms, 메모리 제한 1024 MB.

세 양의 정수 aa, bb, cc가 주어질 때, 다음 조건을 만족하는 정수 쌍 (x,y,z)(x, y, z)의 개수를 구하시오.

  • 1≤x≤a1 \le x \le a
  • 1≤y≤b1 \le y \le b
  • 1≤z≤c1 \le z \le c
  • (x mod y)=(y mod z)=(z mod x)(x \bmod y) = (y \bmod z) = (z \bmod x)

(A mod B)(A \bmod B)는 AA를 BB로 나눈 나머지를 의미한다.

입력

첫째 줄에 테스트 케이스의 수 TT가 주어진다. (1≤T≤600 000)(1 \le T \le 600\,000)

다음 TT개의 각 줄에는 세 정수 aa, bb, cc가 공백으로 구분되어 주어진다. (1≤a,b,c≤100 000)(1 \le a, b, c \le 100\,000)

출력

한 줄에 하나씩 정답을 출력한다.

예제1

  1. 예제 1

    입력
    2
1 2 3
3 2 4
    예상 출력
    1
2