Memoirs of Fili and Kili

All submissions for this problem are available.
The journey was a long and arduous one. And most of them started getting bored, sitting on their horses all day with nothing to do. Some of them (read Fili and Kili) were even beginning to be vocal about it. To shut them up, Gandalf decided to give them a puzzle to keep them occupied. Fili and Kili were really good with numbers (so they said), so Gandalf decided to make the problem a little more difficult for them.
Gandalf has an even number of gold coins in his pocket – ‘p’ pairs to be precise and he would provide some clues to Fili and Kili so that they can come up the right answer as to what the value of ‘p’ is.
If there is another number ‘x’ which is divisible by both ‘a’ and ‘b’ such that the product ‘ab’ is equal to ‘x’ itself and a^{ᵠ(b)}≡ 1 (mod b) where ᵠ(b) gives the number of positive integers (<=b) that are relatively prime to ‘b’. ‘p’ is equal to the sum of integers present in all such unique pairs. Find ‘p’.
By unique pairs we mean that (a,b) and (b,a) are same so must be considered only once for computation of p.
For eg:
For a number x let’s say that (a,b,c,d) are it’s factors and (a,b) and (c,d) satisfy the above condition then you have to output a+b+c+d
Input
The first line of the input contains an integer t denoting the number of testcases.
Each testcase contains a single line containing the value of integer x.
Output
For each testcase output a single line containing the value of p.
Constraints
1<=t<=30000
2<=x<=10^{7}
Example
Input: 3 41 18467 6334 Output: 42 18840 9504
Author:  troika_bytes13 
Tags  troika_bytes13 
Date Added:  5022013 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 