题目描述

定义斐波那契数列 $f$ 如下：

1. $f_{1}=f_{2}=1$；

2. $f_{i} = f_{i-1} + f_{i-2}$，其中 $i \geq 3$ 且 $i$ 为整数。

定义当 $y-x$ 是偶数时，$v(x,y) = 1$，否则 $v(x,y) = 0$。

现在给出非负整数 $a$，请问是否存在一对正整数 $p,q$，满足 $p \leq q \leq 2 \times 10^{9}$ 且 $\sum\limits_{i=p}^{q-1}\sum\limits_{j=i+1}^{q} v(f_{i},f_{j}) = a$（也就是要求从斐波那契数列第 $p$ 项到第 $q$ 项中，在不考虑某一项减去自身的情况下，有 $a$ 对数的差值是偶数）？如果存在，输出任意一组解，否则请输出 $-1$。

输入格式

本题有多组数据。

第一行一个正整数 $t$ 表示数据组数。

接下来 $t$ 行，每行一个非负整数 $a$。

输出格式

对于每组数据，若有解输出任意一组可行的正整数解 $p,q(1 \leq p \leq q \leq 2 \times 10^{9})$，否则输出 $-1$。

7
0
1
2
5
44422
1919810
905304292476

2 3
2 4
3 6
-1
114 514
-1
114514 1919810

提示

【样例解释】

计算可得斐波那契数列前 $6$ 项为 $1,1,2,3,5,8$。

对于第 $1$ 组数据，因为 $f_{3} - f_{2} = 2 - 1 = 1$ 不是偶数，所以当 $p = 2, q = 3$ 时结果为 $0$，符合要求。由于解不唯一，$p = 1, q = 1$ 等其他答案也是符合要求的。

对于第 $2$ 组数据，注意到 $f_{3} - f_{2} = 2 - 1 = 1$ 不是偶数，$f_{4} - f_{3} = 3 - 2 = 1$ 也不是偶数，但 $f_{4} - f_{2} = 3 - 1 = 2$ 是偶数。所以当 $p = 2, q = 4$ 时结果为 $1$，符合要求。由于解不唯一，$p = 1, q = 2$ 等其他答案也是符合要求的。

对于第 $3$ 组数据，因为 $f_{6} - f_{3},f_{5} - f_{4}$ 均为偶数，而其他情况均不为偶数，所以当 $p = 3, q = 6$ 时结果为 $2$，符合要求。当然也存在其他满足要求的解。

对于第 $4$ 组数据，可以证明不存在任何符合要求的解。

子任务编号	分值	$t \leq$	$a \leq$
$1$	$10$	$6$	$5$
$2$	$15$	$101$	$100$
$3$		$1001$	$1000$
$4$		$10^{4}$	$2 \times 10^{6}$
$5$	$20$	$1000$	$2 \times 10^{9}$
$6$	$25$	$10^{5}$	$10^{17}$

对于 $100\%$ 的数据，$t \leq 10^{5},a \leq 10^{17}$。