Pyramid
시간 제한2초메모리 제한512 MB
삼각 격자 피라미드에서 세 꼭짓점이 모두 l층부터 r층 사이에 있는 정삼각형의 개수를 여러 질의에 대해 센다.
문제
A side surface of a pyramid can be cut into many equilateral triangles, whose vertices can be grouped into different levels from top to bottom, such that the first level contains one vertex, the second level contains two, and so on.
As the image shows, for example, two adjacent level-k vertices with a level-(k − 1) vertex can form an upright equilateral triangle, and two adjacent level-k vertices with a level-(k + 1) vertex can form an inverted equilateral triangle as well. Also, three vertices at three different levels can form an equilateral triangle, which may be oblique.
If we only consider vertices between level l and level r (inclusive), in how many ways can we choose three equidistant vertices so that they can form an equilateral triangle?
입력
The input contains several test cases. The first line contains an integer T indicating the number of test cases. The following describes all test cases. For each test case:
The only line contains two integers l and r.
출력
For each test case, output a line containing “Case #x: y” (without quotes), where x is the test case number starting from 1, and y is the answer to this test case.
제한
- 1 ≤ T ≤ 3 × 105
- 1 ≤ l ≤ r ≤ 105