Server Time: Mon Oct 26, 2020 6:48 am
Welcome ( logout
B - Chocolates
PDF (English) Ranklist
Time Limit: 2 second(s) Memory Limit: 32 MB

A new type of chocolate arrived in the local shop. The chocolate comes in bars, each bar consisting of N squares. Bars are factory made and only come in sizes which are full powers of two. In other words a single bar has 1, 2, 4, 8, 16, ... squares.

To fully assess the quality of chocolate Mirko must sample at least K squares. His friend Slavko would also like to try some of the chocolate. Since Mirko is in a hurry to try the chocolate himself, he decides to break the bar he bought in pieces, such that he has exactly K squares, and leaves the rest (if any) to Slavko. The bars are a bit brittle, so Mirko can break them only on their exact center. In other words, from one bar with D squares, he can get two bars with D/2 squares.

Write a program that will determine the minimal number of breaks Mirko must perform in order to obtain exactly K squares (not necessarily in one piece). Also, determine the smallest bar size Mirko must buy in order to have at least K squares.

Input

Input starts with an integer T (≤ 10), denoting the number of test cases. Each case starts with a blank line.

The first and only line of input will contain one integer K (1 ≤ K ≤ 106), number of squares Mirko must sample.

Output

Output should contain two integers, separated by a single space. The first integer is the smallest bar size Mirko must buy. The second integers should be the smallest number of breaks.

Sample Input

Output for Sample Input

3

 

6

 

7

 

5

8 2

8 3

8 3

 


Problem Source: COCI 2009/2010, Contest 7
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan