Short II

Problem code: SHORT2

All submissions for this problem are available.

Given a prime number p, find the number of pairs of integers (a, b) such that p < a, p < b and ab is divisible by (a-p)(b-p).

Input

The first line contains the number of test cases t (1 ? t ? 5). Then t test cases follow, each test case consists of a line containing one prime integer p (1 < p < 1012).

Output

For each test case output one line containing the required number. It's guaranteed that this number won't exceed 263-1.

Example

Input:
3
2
23
59

Output:
14
80
116

Explanation:

In the first test case the sought pairs are (3,3), (3,4), (3,5), (3,8), (4,3), (4,4), (4,6), (5,3), (5,12), (6,4), (6,8), (8,3), (8,6) and (12,5).

Author: gennady.korotkevich
Date Added: 30-09-2011
Time Limit: 3 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

How is a=3, b=4 satisfying

rohitkgp @ 1 Dec 2011 07:44 PM
How is a=3, b=4 satisfying the condition that (ab)=(12) is divisible by (a-p/b-p)=(1/2) for (p=2) ??

hey rohit , its not

tsndiffopera @ 1 Dec 2011 09:28 PM
hey rohit , its not (a-p)/(b-p) , its (a-p)(b-p) ...

ohh..thanks!

rohitkgp @ 1 Dec 2011 10:32 PM
ohh..thanks!

What's the constraint for a,b

adu101992 @ 1 Dec 2011 11:58 PM
What's the constraint for a,b Is it also 10^12???????

@adu101992: As there's no

gennady_adm @ 2 Dec 2011 01:22 AM
@adu101992: As there's no such constraint in the problem statement, you have to figure it out by yourself.

k thanks :)

adu101992 @ 2 Dec 2011 10:26 AM
k thanks :)

How cum anything divided by

chandu_333 @ 3 Dec 2011 11:56 PM
How cum anything divided by zero is infinity..for pair (3,4) n for first case ab=12...ab/(a-p)(b-p)....12/(3-3)(4-3)=12/(0)(1)....how?

@chandu_333 The prime number

phantom11 @ 4 Dec 2011 01:50 AM
@chandu_333 The prime number is 2 not 3

@phantom11 thank u

chandu_333 @ 5 Dec 2011 06:39 PM
@phantom11 thank u

Does JS mean Javascript ?

raghavan999 @ 10 Dec 2011 07:57 AM
Does JS mean Javascript ?

Are negative integers

moawalling @ 11 Dec 2011 02:12 PM
Are negative integers permissible for 'a' or 'b'? if p=2 and a= -4, b= 6; then ab= -24 and (a-p)= -6, (b-p)= 4. This gives (a-p)(b-p)= -24 which can also divide ab=24.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions