*“How to arrange 10 soldiers in 5 rows of 4 soldiers each?”*

Although this problem looks impossible, this is a solution:

unit=0.40cm
(16,16)

[linestyle=dashed,linewidth=0.5pt](8,8)8

[fillstyle=solid](8,16)0.40(8,16) [fillstyle=solid](0.3915,10.4721)0.41(0.3915,10.4721) [fillstyle=solid](15.6085,10.4721)0.42(15.6085,10.4721) [fillstyle=solid](3.2977,1.5279)0.43(3.2977,1.5279) [fillstyle=solid](12.7023,1.5279)0.44(12.7023,1.5279)

[linewidth=2pt]-03 [linewidth=2pt]-04 [linewidth=2pt]-12 [linewidth=2pt]-14 [linewidth=2pt]-32

[fillstyle=solid](8,4.95)0.45(8,4.95) [fillstyle=solid](10.9,7.05)0.46(10.9,7.05) [fillstyle=solid](5.1,7.05)0.47(5.1,7.05) [fillstyle=solid](9.8,10.45)0.48(9.8,10.45) [fillstyle=solid](6.2,10.45)0.49(6.2,10.45)

Input

Input consists of several cases,
each with a natural number n between 2 and 10^{8}.

Output

For every case, we must arrange n soldiers in rows, as follows: In a circumference, we choose x different points, where x is odd and at least 3. Then, we draw x straight segments between different pairs of those x points. At the end, we can place one soldier on every resulting intersection, those produced at the ends of the segments included.

For every given n, print the minimum x that allows arranging at least n soldiers.

Public test cases

**Input**

10 11 2 99976869 99976870 99976871

**Output**

5 7 3 14141 14141 14143

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Salvador Roura
- Original language
- Spanish
- Other languages
- Spanish
- Official solutions
- C++
- User solutions
- C++