Hiệu hai bình phương

Cho dãy số gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\).

Yêu cầu: Với mỗi số nguyên \(a_i\), hãy tìm hai số nguyên dương \(x_i, y_i\) (\(0 < x_i, y_i < a_i\)) sao cho \(x_i^2 - y_i^2 = a_i\).

Input

Dữ liệu vào có cấu trúc:

• Dòng 1: chứa số nguyên dương \(n\) (\(n \le 100\));

• Dòng thứ 2: chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(1 \le i \le n\), \(a_i \le 10^6\)). Các số trên cùng một dòng được ghi cách nhau bởi dấu cách.

Ràng buộc:

• Subtask 1: \(50\%\) số test (\(50\%\) số điểm): \(a_i \le 10^3\);

• Subtask 2: \(50\%\) số test (\(50\%\) số điểm): \(a_i \le 10^6\).

Output

In ra có cấu trúc:

Ghi trên \(n\) dòng, dòng thứ \(i\) là đáp án của \(a_i\), cụ thể:

• Nếu tồn tại bộ số \(x_i, y_i\) thoả yêu cầu thì ghi ra \(2\) số nguyên theo thứ tự \(x_i, y_i\) (nếu tồn tại nhiều bộ số \(x_i, y_i\) thoả yêu cầu thì ghi ra bộ số có \(x_i\) nhỏ nhất);

• Ngược lại ghi ra \(-1\).

Example

3
15 4 9

4 1
-1
5 4

Note

\(15 = 4^2 - 1^2 = 8^2 - 7^2\), chọn bộ có \(x\) nhỏ nhất là \((4, 1)\). Không tồn tại bộ số cho \(a = 4\) (do \(y\) phải dương). \(9 = 5^2 - 4^2\).