Một cấu trúc bông tuyết ~x~ cánh được xây dựng như sau:

• Ban đầu chỉ có một nút.

• Ở mỗi bước, các nút có ít hơn hai cạnh nối với các nút khác sẽ được nối thêm ~x~ nút mới.

Cho ~t~ truy vấn, mỗi truy vấn cho một số ~n~. Xác định xem có tồn tại cặp số ~x~ và ~i~ nào sao cho sau ~i~ (~x, i > 1~) bước thì bông tuyết có đúng ~n~ nút không. Nếu có in ra ~x~ và ~i~, ngược lại in ~-1~. Nếu có nhiều đáp án, hãy in ra đáp án có ~x~ bé nhất.

Input

Dòng đầu tiên gồm một số nguyên dương ~t~ (~1 \le t \le 5 \cdot 10^5~) — số lượng truy vấn của bài toán.

~t~ dòng tiếp theo, mỗi dòng là một số nguyên dương ~n~ (~1 \le n\le 10^{18}~).

Output

Gồm ~t~ dòng là kết quả của truy vấn thứ ~i~.

Scoring

Sample Input 1

6
1
2
7
13
14
15

Sample Output 1

-1
-1
2 2
3 2
-1
2 3

Sample Input 2

2
68719476735
15690529804

Sample Output 2

2 35
3 21