Undoubtedly you know of the Fibonacci numbers. Starting with

F1 = 1 and F2 = 1, every next number is the sum of the two

previous ones. This results in the sequence 1, 1, 2, 3, 5, 8, 13, . . ..

Now let us consider more generally sequences that obey the

same recursion relation

Gi = Gi−1 + Gi−2 for i > 2

but start with two numbers G1 ≤ G2 of our own choice. We shall

call these Gabonacci sequences. For example, if one uses G1 = 1

and G2 = 3, one gets what are known as the Lucas numbers:

1, 3, 4, 7, 11, 18, 29, . . .. These numbers are – apart from 1 and 3 –

different from the Fibonacci numbers.

By choosing the first two numbers appropriately, you can get

any number you like to appear in the Gabonacci sequence. For

example, the number n appears in the sequence that starts with 1

and n − 1, but that is a bit lame. It would be more fun to start with numbers that are as small

as possible, would you not agree?

Input

On the first line one positive number: the number of test cases, at most 100. After that per test

case:

• one line with a single integer n (2 ≤ n ≤ 109

): the number to appear in the sequence.

Output

Per test case:

• one line with two integers a and b (0 < a ≤ b), such that, for G1 = a and G2 = b,

Gk = n for some k. These numbers should be the smallest possible, i.e., there should be

no numbers a

0 and b

0 with the same property, for which b

0 < b, or for which b

0 = b and

a

0 < a.

Sample in- and output

Input 

5

89

123

1000

1573655

842831057

Output

1 1

1 3

2 10

985 1971

2 7

解题：斐波那契第n项：a[n]=f[n-1]*x+f[n]*y;       //  f[n]：f[1]=0，f[2]＝1；的斐波那契数列。枚举n与y看是否能整除f[n-1]。且除数<=y。

x:斐波那契第一项。y:斐波那契第二项。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define Max(a,b) (a>b?a:b)using namespace std;#define ll long longint main (void){    int f[1005] , ans ;    int  y ,x;    f[1]=0;    f[2]=1;    int i=3;    for( i=3; i<=46; i++)    {        f[i]=f[i-1]+f[i-2];    }    int T;    scanf("%d",&T);    while(T--)    {        scanf("%d",&ans);        if(ans==1||ans==2)        {            printf("1 1\n");            continue;        }        bool bb=0;        for(int i=45 ;  i>2&&!bb; i--)            for(int ty=1; ty<=1000000; ty++)                if(ty*f[i]+f[i-1]>ans)                    break;                else if((ans-ty*f[i])%f[i-1]==0&&(ans-ty*f[i])/f[i-1]<=ty)                {                    y=ty , x=(ans-ty*f[i])/f[i-1] , bb=1;                    break;                }        printf("%d %d\n",x,y);    }    return 0;}