Cho một số nguyên \(n\), trả về số lượng số chính phương nhỏ nhất có tổng bằng \(n\).

Số chính phương là số bình phương của một số nguyên; nói cách khác, nó là tích của một số nguyên nào đó với chính nó. Ví dụ: \(1, 4, 9\) và \(16\) là những số chính phương trong khi \(3\) và \(11\) thì không.

Example 1:

• Input: n = 12
• Output: 3
• Giải thích: 12 = 4 + 4 + 4.

Example 2:

• Input: n = 13
• Output: 2
• Giải thích: 13 = 4 + 9.

Input

• Dòng đầu tiên là số lượng bộ test \(n\)
• \(n\) dòng tiếp theo, mỗi dòng là một số nguyên

Output

• Số lượng số chính phương nhỏ nhất có tổng bằng số nguyên tương ứng mỗi dòng

Example

Sample input 1

2
12
13

Sample output 1

3
2