Square Sum
Time: 2 s
Memory: 128 MB
Memory: 128 MB
Roy was relaxing with his friends one fine afternoon when a fun idea struck him. "Let's make a problem!" he exclaimed. Inspired by the beauty of numbers, Roy crafted a challenge involving perfect squares.
Here’s the challenge:
You are given an integer \(X\). Your task is to determine the minimum number of perfect square numbers whose sum equals exactly \(X\). But there is a condition. You cannot use the same perfect square number more than once.
Some examples of perfect square numbers include: \(1, 4, 9, 16, \) and so on.
Here’s the challenge:
You are given an integer \(X\). Your task is to determine the minimum number of perfect square numbers whose sum equals exactly \(X\). But there is a condition. You cannot use the same perfect square number more than once.
Some examples of perfect square numbers include: \(1, 4, 9, 16, \) and so on.
Input
The input starts with an integer \(T\), the number of test cases. Each test case consists of a single inter \(X\) in separate lines.
Constraint
\(1 \le T \le 10^5\\
1 \le X \le 10^5\)
Output
Print the minimum number of perfect squares to make \(X\). If there is no solution, print \(-1\).
Examples
| Input | Output |
|---|---|
|
2
10 11 |
2
-1 |
Problem Info
| Problem ID | 366 |
| Time Limit | 2000 ms |
| Memory Limit | 131072 KB |
| Moderators | punter |
Statistics
Submit
You need to Login or Registration for submit your solution