You are given an integer N. We call a string S good if it satisfies the following conditions:
Here len(S) denotes the length of string S. For example, the strings "aabb", "abb", "aaa", "bbb", "a" are good but strings "aba", "bab", "bba" are not.
Your task is to find the minimum length of a good string which has atleast N distinct substrings.
Notes
Input
Output
For each test case (in a separate line), output the minimum length of a good string which has at least N distinct substrings.
Constraints
1≤T≤50001≤N≤109
In the first test case, we have N=5, possible good strings are "abb", "aab". For example, distinct substrings of "abb" are "a", "ab", "abb", "b", "bb". It can be proved that no good string of length less than 3 has at least 5 distinct substrings.
In the second test case, we have N=8, possible good string is "aabb". For example, distinct substrings of "aabb" are "a", "aa", "aab", "aabb", "ab", "abb", "b", "bb". It can be proved that no good string of length less than 4 has at least 8 distinct substrings.