Param loves teasing people and he has started to tease Shubham recently with reasons known only to them. Param offers Shubham that he wont stop until he solves a question for him. Since Shubham is weak with Maths, help him solve this problem.
The question is very simple. Param will give Shubham two numbers K and P. Consider a 2-D Coordinate system with X- axis extending from [-K,K] and Y axis also from [-K,K]. Param asks Shubham to count the number of rectangles that can be formed in this coordinate system with all 4 corners lying on integral coordinates.
Integral coordinates refer to all points (x,y) such that both x and y are integers and lie in the range [-K,K].
Since answer could be very very large , print (4*ans)%P. It is guaranteed that P is a prime number. (Do not forget to multiply your answer by 4 and then take modulo).
NOTE:-You are not allowed to use JAVA/PYTHON/PYTHON3 for this question
**INPUT** :
The Input contains an integer T and P denoting number of test Cases and the prime number P . T lines follow. Each line contains an integer K.
**OUTPUT** :
For each test case, you have to print (4*ans)%P in a newline.
**CONSTRAINTS** :
1<=T<=100000
1<=K<=10^7
2<=P<=10^9 (30 Points)
2<=P<=10^16 (70 Points)
Since K=1, and P=5, X axis extends from [-1,1] and Y axis also extends from [-1,1]. We can generate
4 Rectangles of 1*1
2 Rectangles of 1*2
2 Rectangles of 2*1
1 Rectangle of 2*2
Hence total 9 Rectangles. So, output is (4*9)%P = 36%5 = 1.