A string is made of only lowercase latin letters (a,b,c,d,.....,z). Can you find the length of the lexicographically smallest string such that it has exactly sub-strings, each of which are palindromes?
Input Format
The first line of input contains single integer - the number of testcases.
T lines follow, each containing the integer .
Constraints
Output Format
Output exactly lines. Each line should contain single integer - the length of the lexicographically smallest string.
Sample Input
2
10
17
Sample Output
4
7
Explanation
for , one of the smallest possible strings that satisfies the property is aaaa.
All palindromes are
- a,a,a,a
- aa, aa, aa
- aaa, aaa
- aaaa
Note
Two sub-strings with different indices are both counted.