3 KHANS of Bollywood are planning to work together in a film called "Three Khans". Aamir (being perfect :P) wants the Alia to be a main lead. But Alia (being very famous :P) is confused that whether to work in a film or not. So they all have decided to play a game called "Filmy Sequence".

According to this game, Aamir will give any number to Alia to play with it. Alia has to find two other numbers using it. Those two numbers represent Stardom of Salman and Srk. These two numbers should be found in such a way so that both numbers will have same number of set ('1') bits in their binary representation as Aamir's number contains. One thing is also need to be checked that Salman's number should be just next greater number to Aamir's number and Srk's number should be just next smaller number to Aamir's number (i.e. in a order of their Stardom :P). They all have decided that if this "Filmy Sequence" forms a G.P (Geometric Progression) then Alia has to be in the favour of movie else not. Alia needs your help to find the probability that she will work in a film and she also wants to find the mean of the Stardom of Salman over Srk.

Note: All the three numbers should be positive and in a range up to 32 bits, and if not possible assume -1. (i.e if particular number is not possible with respect to Aamir's number, assume it as -1).

Input

The first line will have a number of numbers that Aamir will give (t) next t lines will have Aamir's number (n).

Output

Print the asked probability and mean. Any results within 10^-6 absolute error will be accepted.

Constraints

t ≤ 1000000

0 ≤ n ≤ 1000000

Example

Input 1:
3
1
2
3

Output 1:
0.333333 4.000000

Input 2:
2
5
6

Output 2:
0.000000 3.500000

Explanation

Case 2 : 5 → 3, 5, 6 and 6 → 5, 6, 9 are the required numbers.