“War” is the name of a classic board game, pretty famous in Brazil. In this game, the players share the rule of the whole world as each one of them is the leader of one or more territories. Each player can have a different objective but, in general, the more territories a player has the best and they all go for it. Each territory is occupied by one or more “armies” of the player who owns it. In each turn, the players have the opportunity to use the armies in a territory to attack another one and try to conquer it. When attacking, at least one army must remain on the origin territory, so a player with 3 armies can only use 2 of them to attack an adjacent territory. The defense, however, can use all the available number of armies to defend, up to a maximum allowed number of armies. For that matter, the maximum number of armies either an attacker or a defendant can use in a single combat is 3. It means that for any number of armies greater than or equal to 4 on the attacker territory, only 3 can be used at the same time on an attack. Equally, for any number of armies greater than or equal to 3 on the defender territory, only 3 can defend a territory at the same combat as well. The combat takes place by rolling normal 6- faces dices. Both the attacker and the defender roll one dice for each of the armies they are us- ing in the current combat. Then, the following rule determines how many armies are lost by each side in the combat: • First, the results from both sides are ar- ranged in a non-increasing order; • Then, the highest value from the attack is compared with the highest value from the defense, the second highest is com- pared with the second highest and so on, until one of the sides has no more dices to compare with; • Finally, during the comparison of an attack dice with a defense dice, the attack wins if it has the highest score (note that the defense wins in case of a tie in the dices); For example, if the attack rolls 3 dices and obtains the values 3, 6 and 5 while the defense rolls 2 dices and gets 4 and 6, the comparisons will be of 6 against 6 (and the defense wins) and 5 against 4 (and the attack wins), resulting in the loss of one army for each side. ItÂŽs good to mention that a player can raid several consecutive attacks to an enemy territory on the same round (each of them using the remaining soldiers and respecting the limit of 3 per attack). It should not be a surprise that usually each player uses as many armies in a combat as he can, even though the rules allow him to use less. On the other hand, some players are a little bit neurotic and when they start attacking an enemy territory, they donÂŽt stop until having conquered that territory (i.e. the defender has no army) or they canÂŽt attack anymore (i.e. the attacker has only 1 army). Elbdson is one of these neurotic players. But he is also a great computer programmer. Then, when he decided to invite his friends Wedbio, Herblex and Al-Hirai to play War in his house, the first thing he
2/2 thought of was to write a program that determines if he has some advantage when attacking an enemy. In other words, Elbdson wanted to know how many armies he needed in a particular territory to raid an attack against an enemy territory with X armies and have more than 50% of chance to conquer that territory. LetÂŽs see if you can do the same calculation. Input The input file contains several input sets. Each set is composed of an integer X (1 ≤ X ≤ 1000) in a line itself, representing the number of armies in the enemy territory. Input is terminated by a set where X = 0. This set must not be processed. Output For each input set produce one line of output, the minimum number of armies that Elbdson needs, to attack the enemy territory and have a probability of conquer it greater than 0.5. Sample Input 1 2 3 0 Sample Output 3 4 6