At first, there are n people numbered 1 to n around a circle and every second remaining person will be eliminated until only one survives. Let the number of the survivor be x. The process is then repeated with x number of people and let the survivor number is y. The process then starts with y number of people and so on. The repetition ends when the survivor is in the last position in the circle.

Example with n = 5: after the first elimination round, the survivor is person 3. Because this is is not the last person in the circle, a new elimination round with 3 people is started. Now person 3 survives, so we can stop.

Input

The first line is an integer representing the number of test cases. Each of the test cases follows below. Each test case consists of an integer representing n (0 < n ≤ 30000).

Output

For each test case, print the serial number of the case, a colon, an space, total number of repetitions (the number of times the elimination process is done after the initial elimination round with n people), a space and the position of the survivor at last.