Count triples | Practice Problems

Count triples

★★★★★

3.7

9 votes

Combinatorics, C++, Number theory, Implementation, Basics of Combinatorics, Math

Details

Submissions

Discussion

Editorial

Problem

You are given 2 integers N and K. Your task is to count the triplets of the form (x, y, z) while meeting these conditions:

x + y + z = N
0 < z ≤ y ≤ x
|x - y - z| > K

Important: Use a FAST I/O

Input

The first line contains a single integer T denoting the number of test cases.
For each test case, the only line of input contains 2 space-separated integers N and K.

Output

For each test case, print the count of triples of the form (x, y, z), while meeting the given conditions, in a separate line.

Constraints
$1 ≤ T ≤ 10^6 \\ 0 ≤ K ≤ N ≤ 10^9$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

In the first test case, we have $N = 6, K = 0$ . The 2 triples satisfying the conditions are $(4, 1, 1), (2, 2, 2)$ .

In the second test case, we have $N = 12, K = 3$ . The 5 triples satisying the conditons are $(10, 1, 1), (9, 2, 1), (8, 3, 1), (8, 2, 2), (4, 4, 4)$ .

In both above samples, it is easy to verify that all 3 conditions hold and there are no other triples satisfying the conditions.