SPOJ.com - Problem CT2

CT2 - Counting triangles 2

no tags

Consider a 2D integer grid with lower left corner at (0, 0) and upper right corner at (X, Y).
We are interested in isosceles right triangles with all the 3 corners at the grid nodes (integer coordinates).

Input

The input begins with the number T of test cases in a single line.
In each of the next T lines there are two integers X, Y.

Output

For each test case, on a single line, print the number of such triangles.

Example

Input:
2
0 3
1 1

Output:
0
4

Constraints

1 <= T <= 10^4
0 <= X <= 10^4
0 <= Y <= 10^4

Information

Your challenge is to give in time the answer with the shortest code.
This problem is CT with more challenging constraints. Source limit is 512B
My poorly golfed Py3 code scored 158B in 0.87s (for two input files). (time updated 2017-02-11 ; compiler changes)

Submit solution!

hide comments



	shubhankaryash: 2015-05-29 16:44:15 can u give some more test cases? =Francky=> No other test case is provided. Solve CT first should be enough for other test cases. Last edit: 2015-05-31 20:03:55
	Francky: 2014-06-05 09:43:55 I've increase a little time limit for slower languages. --edit,Francky--> But it's perhaps not a good idea ; ... @Mitch : as you used another complexity, competitive with faster language ; what do you recommend ? (eg : CT3 with higher constraints ? saying 10^9, answer modulo 109+7) ??? (Mitch) So far I've solved/golfed this problem in two different complexities, but not the intended one. Also, I'm not sure what languages are fast enough to pass with my current approach under these constraints. It's hard for me to make a recommendation under the current circumstances, but it could be a non-issue if the intended complexity continues winning (right now 158 vs. 169). --(Francky)--> Congrats, you broke the record. And now, what do you recommend ? --edit(Francky)--> Some experiments done as you asked, results by mail. Back to initial 5s per file. Last edit: 2014-06-06 13:56:25**

Submit solution!

Added by:	Francky
Date:	2014-06-04
Time limit:	5s
Source limit:	512B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64