Chocolates

All submissions for this problem are available.
Alice is teaching a class of N+1 students and she is planning a picnic for her students. Each of her students is given a distinct rank between 0 and N for identification which makes sure they don’t get lost during the picnic. She has brought with her many bags each completely filled with N^{2}chocolates. She wants to distribute them among her students. But, like every other teacher, she is not going to give them without making them do some math problems first. So, she asks each of her students to choose a number k equal to his/her rank, and do the following :
 Find out the number of ways of selecting k chocolates from a set of N distinct chocolates.
 Add his/her rank to N to get N’ and again find out the number of ways of selecting k chocolates from a set of N’ distinct chocolates.
She will give each of her students x * y chocolates, where x is the number that the student computed in the first step and y is the number computed in the second step. Now after calculating how many chocolates she will give in total, she starts taking them out from her bags. She picks a completely filled bag at first and starts taking out chocolates out until the bag is empty. Then, she chooses another completely filled bag and follows the same procedure. She wonders how much chocolates she will have to remove from the last bag.
As a programmer, she asks for your help to find out the number of chocolates she will have to remove from the last bag.
Input
The first line of the input contains an integer T denoting the number of test cases. Next follow T lines each containing an integer N for the test case. Assume that N is guaranteed to be a prime number.
Output
For each test case, output one line containing the number of chocolates Alice needs to remove from the last bag.
Constraints
 1 ≤ T ≤ 10^{5}
 1 ≤ N ≤ 31113
Example
Input: 1 2 Output: 1
Author:  iopc_admin 
Tags  iopc_admin 
Date Added:  7032013 
Time Limit:  0.147436 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, GO, PYP3 
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. 