CF1656D K-good

We say that a positive integer $ n $ is $ k $ -good for some positive integer $ k $ if $ n $ can be expressed as a sum of $ k $ positive integers which give $ k $ distinct remainders when divided by $ k $ . Given a positive integer $ n $ , find some $ k \geq 2 $ so that $ n $ is $ k $ -good or tell that such a $ k $ does not exist.

The input consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^5 $ ) — the number of test cases. Each test case consists of one line with an integer $ n $ ( $ 2 \leq n \leq 10^{18} $ ).

For each test case, print a line with a value of $ k $ such that $ n $ is $ k $ -good ( $ k \geq 2 $ ), or $ -1 $ if $ n $ is not $ k $ -good for any $ k $ . If there are multiple valid values of $ k $ , you can print any of them.

$ 6 $ is a $ 3 $ -good number since it can be expressed as a sum of $ 3 $ numbers which give different remainders when divided by $ 3 $ : $ 6 = 1 + 2 + 3 $ . $ 15 $ is also a $ 3 $ -good number since $ 15 = 1 + 5 + 9 $ and $ 1, 5, 9 $ give different remainders when divided by $ 3 $ . $ 20 $ is a $ 5 $ -good number since $ 20 = 2 + 3 + 4 + 5 + 6 $ and $ 2,3,4,5,6 $ give different remainders when divided by $ 5 $ .