After defeating Mandarin in Iron man 3, Jarvis is most of time free and now he has started playing with numbers. Jarvis being an AI (Artificial Intelligence) solves almost all the riddle given by Tony Stark very quickly. This time Tony gave him a problem about base conversion’s but the problem statement given by Tony seems to be confusing and Jarvis asked for Help! Problem Statement – “123 when converted in base 16, it consist of two digits 7 and 11 so the sum of the numbers is 18,(For Given N) Find denominator of average(irreducible form) of sum of all the numbers formed on conversions from base 2 to N-1”.

Can you help Jarvis?

Input:

First line will have the number of test case (t) and then t subsequent lines will contain a number N.

Output:

For every test case, give answer in new line.

Constraints:
$T < 10$
$3 <= N <= 1000$