Fibonacci Problem Solving Strategy

Time limit2sMemory limit256 MB

Summary

Find the smallest starting pair (a, b) with 0 < a <= b whose Fibonacci-like sum sequence contains n.

Level: Medium7 of 10
Topics: Number theory, Math
Solved: No attempts yet

Problem

A Gabonacci sequence starts with G1=a and G2=b (0<a≤b) and follows Gi=Gi-1+Gi-2 for i>2. For each n, output the lexicographically smallest pair (a,b) such that n appears in the sequence. Compare pairs by smaller b first, then smaller a.

Input

The first line has T (T≤100). Each following line has n (2≤n≤10^9).

Output

For each test case, print a and b on one line.

Examples4

Example 1

Input

Expected output

Example 2
Input
```
1
13
```
Expected output
```
1 1
```
Example 3
Input
```
1
2
```
Expected output
```
1 1
```
Example 4
Input
```
2
21
34
```
Expected output
```
1 1
1 1
```