New Fibonacci Sequence Problem

Given a positive integer \(x\), it is known that \(x\) is a term in a new Fibonacci sequence \(f_a\) defined by a parameter \(a\) (with \(a \ge 1\)) as follows:

• \(f_a(1) = 1\);
• \(f_a(2) = a\);
• \(f_a(n) = f_a(n-1) + f_a(n-2)\) for \(n > 2\).

For example, when \(a = 4\), the sequence is \(f_4(1)=1,\ f_4(2)=4,\ f_4(3)=5,\ f_4(4)=9,\ f_4(5)=14,\dots\).

You are given a number \(x\) which is a term of some new Fibonacci sequence \(f_a\) but the values of \(n\) and \(a\) are unknown. Your task is to find all pairs of integers \((n, a)\) with \(n \ge 2\) such that

[ f_a(n) = x \quad \text{.} ]

Note: For \(n \ge 3\), one can deduce that \[ f_a(n) = F(n-1) \cdot a + F(n-2), \] where \(F(1)=1,\ F(2)=1,\ F(3)=2, \ldots\) denotes the standard Fibonacci sequence. In the case \(n=2\), we simply have \(a=x\).

Output all pairs \((n,a)\) in increasing order of \(n\). Each pair should be printed on a separate line with \(n\) and \(a\) separated by a space.

inputFormat

The input consists of a single line containing a positive integer \(x\) (\(x \ge 1\)).

outputFormat

Output each valid pair \((n, a)\) on a separate line in increasing order of \(n\). Each line should contain two space-separated integers representing \(n\) and \(a\) respectively.

sample

1

2 1