P14021 [HackerEarth] The JoyFest at SVNIT comes to end. In the closing ceremony, a joyful cake is distributed among all visitors and volunteers. There is a huge cake, but the crowd is even larger in number.
普及
题目描述

The JoyFest at SVNIT comes to end. In the closing ceremony, a joyful cake is distributed among all visitors and volunteers. There is a huge cake, but the crowd is even larger in number. Janit, coordinator of JoyFest cuts the cake.

Janit knows how many people are there and he wishes to give only one piece of cake to each person. Janit has his own way of maximizing number of pieces. For each cut, he tries to make maximum possible smaller pieces after that cut. The cake is circular and each cut follows a straight line that passes through the circle twice. There will be no half-cuts or semi-cuts. (Picture demonstrating what is cake cut mean as described in statement.)

He wants you to help in determining what is the minimum number of cuts he should make so that every person gets at least one smaller part of the cake.
(With this kind of distribution, every person will not get same size of cake and he is not bothered of it.)
Input:
First line contains number of test cases T.
T lines follows. Each test case consists of a number N denoting number of persons(min no. of pieces he should make).

Output:
For each test case, print a number denoting number of cuts Janit should make on the cake.

Constraints:
1 ≤ T ≤ 10^6
1 ≤ N ≤ 10^12

Large input files. Use faster i/o methods.

Problem Setter : Vinay Kumar

SAMPLE INPUT
3
3
4
12

SAMPLE OUTPUT
2
2
5

输入格式

见题面

输出格式

见题面

样例输入
115 1 2 3 4 5 6 7 8 10 9 21 22 13232131 221315 1646521651 146690 784997 603730 837226 628850 112226 148997 242065 421202 177242 131045 730 476101 3482 582170 857477 291601 181477 29585 541697 44522 135425 321490 184042 611525 280901 743045 15130 4490 18226 863042 643205 485 3365 4762 27890 154450 207937 122 1765 52442 139130 177242 844562 614657 288370 39205 104977 99226 136901 170570 276677 8282 960401 913937 762130 743045 28901 992017 78962 93026 855626 7057 106930 112897 255026 715717 531442 97970 734450 15377 801026 338725 297026 662597 134690 188357 132497 1850 562501 7570 652865 76177 31685 620945 341057 162410 423802 568517 159202 868625 3601 456977 135425 546122 145 51077 343397 8837 290522
样例输出
0 1 2 2 3 3 3 4 4 4 6 6 5144 665 57385 12753 6992 6131 6030 891 851 7464 4707 1004 12449 7765 383 7896 4774 5455 13688 13511 8586 6370 2912 2383 8388 7418 5920 9536 12845 7928 7218 5319 6288 931 12913 13279 1902 4803 28 11738 7108 4735 7583 5416 7343 2809 13312 12117 8263 7699 11486 11690 14069 9240 14073 8316 2516 693 12693 10202 8621 5770 10362 767 1541 9134 8888 12428 8778 8917 10024 1744 13653 3465 7160 1694 1114 1172 13811 9378 8871 5996 6927 3640 1095 1698 11956 12594 2391 5347 8654 5855 11117 13858 1462 7501 8850 10351 5787 3486 5127 1669 71 13620 14117 2073 1172 1090 3246 9825 5309 12117 1679 12236 1615 11758 8777 8412 10209 6009 8601 13705 11864 5576 8262 8168 7918 2970 4377 13705 1297 4344 10215 10351 12806 10191 12424 13978 6122 1527 9660 11431 8487 6182 4367 4943 12780 7985 8197 3688 13994 2656 12234 6558 3073 6354 584 10993 4165 13944 10556 5462 13131 1471 1672 11795 11662 8936 11632 12625 5306 1991 4755 13793 3014 3963 13576 10635 11947 7631 182 11800 5128 12417 4216 8202 4630 13783 14036 8795 13585 10450 9099 12574 6761 5612 10228 13264 406 2558 11746 5712 13533 11343 204 11389 1164 13782 7881 13113 2111 8064 5612 7241 1181 4668 1301 652 4309 1195 4288 12735 6486 8228 11168 13248 13839 2094 12370 9088 13636 4817 9641 7867 2018 4687 14097 3182 4326 7838 11136 1278 10742 11588 8519 6764 2114 4661 7416 1264 697 6546 14001 7184 632 11027 1131 9314 7962 8342 4260 2297 8000 8741 10164 10018 13428 10120 8043 12595 12799 14019 13875 9399 11466 8252 11005 8422 7756 4279 9687 8453 5667 9546 10478 6300 1271 6450 1472 9233 652 573 11530 3493 9314 2393 8354 3442 7354 2254 1895 6010 11114 10611 10252 3280 13705 7115 11703 7319 6235 7248 1629 11903 11635 12108 4062 12906 4417 375 2838 14052 948 9209 12387 5102 6443 6599 3386 13798 8853 123 508 666 10734 10759 3947 10297 12715 1508 3473 13793 3596 14087 11554 10072 6894 10457 3677 6152 10831 1356 904 6620 5407 13291 6563 11850 5747 4791 6347 9441 4914 6856 10107 1506 12456 8895 6645 5872 10403 4960 5523 8840 4904 2934 13753 6640 8232 3288 12793 4921 13627 13697 6382 4892 12845 7787 11584 13434 12578 3789 8733 12333 5486 4698 13841 3801 13595 1185 9673 4697 6145 1054 8379 5892 12971 2831 12531 7061 962 6023 6824 447 5578 8047 5340 13264 1691 2782 12555 9112 1411 7146 7303 6899 6686 1843 10700 980 3028 1072 518 4015 2126 3738 9907 9938 6570 3137 2857 7532 9161 9680 2820 9580 3585 8160 3544 117 5783 1957 9229 7196 3946 11375 14094 5473 13217 5493 1294 11087 6565 10795 960 3531 392 10867 13469 1803 8844 11167 4176 12847 6705 6996 8286 5131 9998 11830 5248 1639 8628 9320 3676 7415 6552 3627 12888 468 3961 9023 11556 5367 5677 12516 3739 909 4081 3066 2712 12927 9074 1730 11632 1636 8726 617 1608 4582 7287 1698 1063 1775 11018 4739 9190 12411 3209 2778 12879 7170 11800 5135 7379 12318 3509 11119 13227 2432 9027 10781 10201 3958 12510 7690 5596 7095 3149 2045 6518 10437 3743 7582 7053 619 12322 11085 7872 1389 13862 1451 3400 6361 6586 10779 13521 4936 7757 12606 7368 2642 9246 3427 6600 7614 5959 7037 9550 9109 9083 1928 245 12827 9509 7299 8289 2530 4241 2018 12902 12944 3469 2161 4 4896 7781 13526 9833 10379 11991 12042 7862 1936 1328 9304 9550 2128 2199 13943 6078 6124 1728 1164 13793 11237 8463 2780 8610 7545 4798 7369 6347 3110 4371 1194 8006 12154 577 12680 3231 7409 10581 11095 9345 6750 6256 13738 3719 3297 13538 9798 9421 10107 10962 3913 2044 124 6693 10653 7669 6333 3882 8859 4284 8253 10052 12291 1106 5470 5670 4339 7722 2109 1291 11908 3700 2389 6344 7419 5685 5740 3075 9948 10689 8878 13861 12734 9003 1253 9245 11513 2428 7968 6230 6712 11063 11123 13844 7010 11435 5373 11349 5015 2322 7481 2780 6023 9870 3967 13442 10397 4548 11359 6203 1096 6095 764 13830 9939 11000 3773 7310 13428 11742 8382 5999 8663 204 5701 1532 11639 11073 7723 11495 13397 1062 9117 119 5774 13084 13561 2029 3490 10778 3073 4586 11714 12820 4274 7511 9679 8048 9663 8965 489 12886 822 3994 13090 6524 5525 10588 12438 8089 2782 6534 3994 11899 6652 4609 10841 914 1479 9174 6532 4552 13760 4105 3231 12876 6457 7751 1624 1978 2574 2113 723 12380 6107 8655 13745 6473 5101 12041 9405 2724 13417 13398 482 768 3865 6165 1681 5344 1196 8215 4738 9799 7162 2810 8533 13619 10561 10157 10440 7978 7111 11162 6215 8058 5675 5818 389 5617 12700 4634 3183 6815 3891 3666 7584 2596 9830 4107 2782 5869 12322 2362 1526 5341 5172 4900 13803 10575 9898 10100 13394 2867 1962 5467 10925 2479 6126 6155 2937 13667 10790 6121 6341 9522 9786 13926 12120 317 3891 9743 1027 11055 12104 2553 11237 12118 2294 10898 8552 12192 1697 2645 916 3660 2953 6682 6139 9079 7678 9076 8604 13309 1056 9786 8690 5684 9570 1509 6001 8303 11251 7027 57 4056 4421 6135 2032 6715 11875 5425 4764 13572 8070 522 3090 11022 2045 4070 800 4565 13148 4245 3732 9045 14033 7263 587 4302 3613 1430 7446 724 3298 2343 4780 7720 8480 1653 9276 6213 7078 8883 484 9989 4245 12558 6869 1133 2486 2510 5698 10475 6756 4271 219 1488 11536 808 5791 1007 11220 8078 10714 376 10423 10335 2937 4760 11988 12215 5814 13907 1796 6297 9754 6042 4714 11464 7174 2042 13974 7713 12517 1430 11985 12738 2918 4220 8386 3550 68 305 11629 10783 682 7910 1817 12603 7511 8648 5517 13325 8413 7313 5480 13009 8195 5036 10331 1229 7078 5005 8942 294 6435 1626 13032 4193 5846 2117 7744 5916 2423 72 11540 12089