#P17765. 「LDOI R2」平方数 / Square
「LDOI R2」平方数 / Square
Problem Description
There are given pairs .
A sequence of length is considered a good sequence if and only if it satisfies the following conditions:
-
are different from each other.
-
is a perfect square.
-
is a perfect square.
-
, is a perfect square.
Find the minimum value of among all good sequences, or output if there are no good sequences.
Input Format
There are multiple test cases for this problem.
The first line contains an integer , representing the number of test cases. Next, for each test case:
The first line contains an integer .
The next lines each contain two positive integers. The two numbers in line represent .
Output Format
For each test case:
If there are good sequences, output the minimum value of among all good sequences. If there are no good sequences, output .
3
5
4 5
20 9
8 9
16 3
12 2
1
1 1
2
1 1
1 1
2
-1
2
1
9
5 9
8 2
9 3
5 4
6 5
3 5
2 4
8 5
9 3
3
Hint
Explanation
Sample Explanation: For the first test case, consider the sequence , , , are all perfect squares, and the length of the sequence is . is also a good sequence, but its length of is not optimal.
Constraints
This problem uses subtask scoring.
| Subtask | Score | |
|---|---|---|
For all test cases, ,.
Hint
is a perfect square if and only if there exists an integer that satisfies .