# PROBLEM LINK:

# DIFFICULTY:

Easy

# PREREQUISITES:

Mathematics, Factorization

# PROBLEM:

Find the smallest perfect square X > 0 such that N + X = Y where Y is another perfect square.

# EXPLANATION:

Let N + b^2 = a^2

\implies N = a^2 - b^2

\implies N = (a + b)(a - b)

Thus, we can find the factors of N. We iterate i from 1 to \sqrt{N} and if i is a factor of N then, so is \frac{N}{i}.

Considering a + b = \frac{N}{i} and a - b = i

\implies b = \frac{\frac{N}{i} - i}{2}

We find the minimum value of b over all possible values that satisfy N + b^2 = a^2.

If there is no such value, the answer is -1.

Time Complexity: \mathcal{O}(\sqrt{N}) per test case.

# SOLUTION:

```
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main () {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int a, b;
bool possible = false;
ll ans = -1;
for (int i = sqrt(n); i >= 1; --i) {
if (n % i == 0 && i != (n/i)) {
a = (n/i + i)/2;
b = (n/i - i)/2;
if (b*b + n == a*a) {
possible = true;
if (ans == -1) {
ans = b;
} else {
ans = min(ans, 1ll*b);
}
}
}
}
if (possible) {
ans = ans * ans;
}
cout << ans << endl;
}
return 0;
}
```