스누피가 동전을 3개 주웠다. 어느날 스누피는 동전을 던져 그것을 모두 앞면 또는 뒷면으로 만들고 싶었다. 몇 번을 해보니까 최소 2 번의 뒤집음을 하지 않고는 모두 앞 또는 뒤로 만들수 없었다.

동전은 한번에 하나만 뒤집을수 있고 동전을 한번이상 뒤집을수 있다.

n개의 동전이 있을때 최소의 뒤집음 수 x를 구하여라. 단, n개의 동전이 만들어내는 모든 가짓수에 대해서 x번의 뒤집음을 반드시 해야한다.

예로 3 개의 동전을 던질 경우

- 앞 앞 앞 
- 앞 앞 뒤
- 앞 뒤 뒤
- 뒤 뒤 뒤 

입력

각 입력에 대해 동전의 수 n ( n < 10,000 ) 이 주어지고 , 입력의 끝은 0 이다.

출력

답이 없는 경우 “No Solution!” 을 출력한다.

입출력 예

입력

2
3
0

출력

No Solution!
2

문제 보충 설명

동전이 3개일때 경우는 아래의 4가지 입니다. 
(O 앞면, X 뒷면) 

O O O 
O O X 
O X X 
X X X 

이 4가지 경우 2번만 뒤집으면 모든 동전을 앞 혹은 뒤로 바꿀 수 있습니다. 

O O O -> O O X -> O O O 
O O X -> X O X -> X X X 
O X X -> O X O -> O O O 
X X X -> X X O -> X X X 

이렇게, 동전 n개를 가지고 나올 수 있는 모든 경우에 대해서, n개의 모든 동전을 앞 혹은 뒤로 만들기 위한 공통적인 최소 뒤집힘
횟수를 구하는 것이 문제 입니다..... 설명: makecode 



동전이 3개 일 땐 나올 수 있는 경우의 수가 아래와 같죠?? 

- 앞 앞 앞  
- 앞 앞 뒤 
- 앞 뒤 뒤 
- 뒤 뒤 뒤  

이 때 한 번만 뒤집어서 모두 앞 이나 모두 뒤를 나올 수 있겠나요?? 
무조건 한 번은 뒤집어야 되요.. 

이럴 경우에  
- 앞 앞 뒤 
- 앞 뒤 뒤 
는 한 번만 뒤집어도 가능 하지만.. 

- 앞 앞 앞 
- 뒤 뒤 뒤  
는 한 번만 뒤집으면 모두 앞, 뒤 가 아니게 되죠 

그 다음에 두 번 뒤집어서 모두 앞 이나 뒤가 나올 수 있는지 보면. 
- 앞 앞 앞 
- 뒤 뒤 뒤  
경우에는 같은 동전을 두 번 뒤집으면 모두 앞 이나 뒤가 나오 겠고.. 
- 앞 앞 뒤 
- 앞 뒤 뒤 
경우에는 첫 번째는 앞 두 개를 뒤집고 두 번째는 뒤 두 개를 뒤집으면 가능하죠 

그래서 최소의 뒤집힘 수가 2 번이 되는거예요 ....설명: maybemaster 

출처: POJ Monthly--2007.04.01, Snoopy