Lock and Key

All submissions for this problem are available.
The beagle boys started working in a lockandkey manufacturing factory. The factory uses a newly purchased robot to pack a batch of N locks and their keys. On a day, T batches of locks and keys are manufactured. The locks and keys are manufactured separately at two different wings of the factory. They then arrive at the packing section, where the robot packs them in pairs. Locks in a batch are numbered from 1 to N. Their corresponding keys are also numbered the same. The job of the robot is to pick up a lock, find the corresponding key, and pack it together. However, due to a programming error, the robot uses the following procedure to pack them:
Pick up lock number 1. Pick up a random key from the batch of N keys. Pack them together. Then keep on picking up locks in the order 2, 3, ..., N. Look for the key with the same number on the lock. If found, pack the matching set together. Otherwise, pick a random key from the remaining keys in the batch, and pack them together.
Now, beagle boys were freshly out of jail, and wants this job badly. The only option before them is to report the above problem to the boss, before the boss finds this out. Of course, the boss will fire them, if he finds this out first, as he would think that beagle boys are the ones who are messing up.
Beagle boys has prepared a report on this issue. They also want to include some statistical analyses in the report. Help them to find the probability that the lock numbered N is packed with the key numbered N.
Input
First line contains a single integer T, the number of batches manufactured per day.
Then T lines follow, one per test case.
Each line contains an integer N, the number of locks (and keys) in a batch.
Output
For each test case, output on a single line, two space separated integers p and q such that gcd(p, q) = 1 and the required probability is p / q.
Constraints
1 ≤ T ≤ 25
1 ≤ N ≤ 500
Example
Input: 1 2 Output: 1 2
Explanation
There are 2 locks (and keys). The only two possibilities are {L1K1, L2K2} and {L1K2, L2K1}. Clearly, the required probability is 1/2. (So, p = 1 and q = 2).
Author:  tijoforyou 
Tags  tijoforyou 
Date Added:  22032013 
Time Limit:  0.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. 