RETO11FEB - TAREA SENCILLA

Given a positive integer n, find another integer p and non-negative integer o such that n = O2P.

Example: For n = 24, o = 3 and p = 3.

Write a program that for each data set:

  • Read a positive integer n,
  • calculates the whole non-negative integer o and p such that n = O2P,
  • writes the result.

Input

The first line of input contains a positive integer d, indicating the number of data sets, 1 ≤ d ≤ 10

The following lines are data sets. Each data set consists of exactly one line that contains exactly one integer n, 1 ≤ n ≤ 106.

Output

The output consists of exactly d lines, one line for each data set.

Line i, 1 ≤ i ≤ d, corresponding to the i-th entry and must contain two integers o and p separated by a single space so that n = O2P

Example

Input:
2
24
32

Output:
3 3
1 5

Added by:MARATON AFDM
Date:2015-08-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:MAWK BC C NCSHARP CSHARP C++ 4.3.2 COFFEE DART FORTH JAVA JS-RHINO JULIA KTLN OCT PHP PROLOG PYPY3 R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2018-09-24 21:46:36
Output the smallest o for which a solution exists. (o, p) = (n, 0) gets WA despite complying with the constraints.
2015-08-28 07:44:25 Min_25
Moved to Tutorial. Please enable all the languages unless there is a special reason.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.