시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 873 256 173 30.674%

문제

상근이는 초등학교 졸업 여행으로 외계 행성 X3에 방문했었다. 이 행성에 사는 사람들의 이름은 모두 자연수이다. 행성의 거주민은 모두 서로를 알고 있다. 두 X3인은 그들의 친밀도를 자신의 이름을 이진수로 바꾸어서 계산한다. 두 이름을 이진수로 바꾸고, 자리수가 짧은 쪽을 기준으로 정렬한다. 이때, 두 이진수의 각 자리 아래에 두 자리가 같으면 0을, 다르면 1을 적는다. 이 결과 이진수를 다시 10진수로 바꾸면 그들의 친밀도가 된다.

예를 들어, 10과 19의 친밀도는 25이다.

행성의 가치는 이 섬에 있는 모든 친밀도의 합이다. 행성 거주민들의 이름이 주어졌을 때, 행성의 가치를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 X3 거주민의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 다음 N개의 줄에는 거주민의 이름이 주어진다. 이름은 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 행성 X3의 가치를 출력한다.

예제 입력 1

3
7
3
5

예제 출력 1

12
W3sicHJvYmxlbV9pZCI6IjI4MzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1ODlcdWMxMzEgWDMiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWNkMDhcdWI0ZjFcdWQ1NTlcdWFkNTAgXHVjODc4XHVjNWM1IFx1YzVlY1x1ZDU4OVx1YzczY1x1Yjg1YyBcdWM2NzhcdWFjYzQgXHVkNTg5XHVjMTMxIFgzXHVjNWQwIFx1YmMyOVx1YmIzOFx1ZDU4OFx1YzVjOFx1YjJlNC4gXHVjNzc0IFx1ZDU4OVx1YzEzMVx1YzVkMCBcdWMwYWNcdWIyOTQgXHVjMGFjXHViNzhjXHViNGU0XHVjNzU4IFx1Yzc3NFx1Yjk4NFx1Yzc0MCBcdWJhYThcdWI0NTAgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViMmU0LiBcdWQ1ODlcdWMxMzFcdWM3NTggXHVhYzcwXHVjOGZjXHViYmZjXHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWMxMWNcdWI4NWNcdWI5N2MgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViNDUwIFgzXHVjNzc4XHVjNzQwIFx1YWRmOFx1YjRlNFx1Yzc1OCBcdWNlNWNcdWJjMDBcdWIzYzRcdWI5N2MgXHVjNzkwXHVjMmUwXHVjNzU4IFx1Yzc3NFx1Yjk4NFx1Yzc0NCBcdWM3NzRcdWM5YzRcdWMyMThcdWI4NWMgXHViYzE0XHVhZmI4XHVjNWI0XHVjMTFjIFx1YWNjNFx1YzBiMFx1ZDU1Y1x1YjJlNC4gXHViNDUwIFx1Yzc3NFx1Yjk4NFx1Yzc0NCBcdWM3NzRcdWM5YzRcdWMyMThcdWI4NWMgXHViYzE0XHVhZmI4XHVhY2UwLCBcdWM3OTBcdWI5YWNcdWMyMThcdWFjMDAgXHVjOWU3XHVjNzQwIFx1Y2FiZFx1Yzc0NCBcdWFlMzBcdWM5MDBcdWM3M2NcdWI4NWMgXHVjODE1XHViODJjXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YjQ1MCBcdWM3NzRcdWM5YzRcdWMyMThcdWM3NTggXHVhYzAxIFx1Yzc5MFx1YjlhYyBcdWM1NDRcdWI3OThcdWM1ZDAgXHViNDUwIFx1Yzc5MFx1YjlhY1x1YWMwMCBcdWFjMTlcdWM3M2NcdWJhNzQgMFx1Yzc0NCwgXHViMmU0XHViOTc0XHViYTc0IDFcdWM3NDQgXHVjODAxXHViMjk0XHViMmU0LiBcdWM3NzQgXHVhY2IwXHVhY2ZjIFx1Yzc3NFx1YzljNFx1YzIxOFx1Yjk3YyBcdWIyZTRcdWMyZGMgMTBcdWM5YzRcdWMyMThcdWI4NWMgXHViYzE0XHVhZmI4XHViYTc0IFx1YWRmOFx1YjRlNFx1Yzc1OCBcdWNlNWNcdWJjMDBcdWIzYzRcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAxMFx1YWNmYyAxOVx1Yzc1OCBcdWNlNWNcdWJjMDBcdWIzYzRcdWIyOTQgMjVcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdDxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wveDMucG5nXCIgc3R5bGU9XCJ3aWR0aDogMTg2cHg7IGhlaWdodDogNjlweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVkNTg5XHVjMTMxXHVjNzU4IFx1YWMwMFx1Y2U1OFx1YjI5NCBcdWM3NzQgXHVjMTJjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjZTVjXHViYzAwXHViM2M0XHVjNzU4IFx1ZDU2OVx1Yzc3NFx1YjJlNC4gXHVkNTg5XHVjMTMxIFx1YWM3MFx1YzhmY1x1YmJmY1x1YjRlNFx1Yzc1OCBcdWM3NzRcdWI5ODRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkNTg5XHVjMTMxXHVjNzU4IFx1YWMwMFx1Y2U1OFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgWDMgXHVhYzcwXHVjOGZjXHViYmZjXHVjNzU4IFx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMSwwMDAsMDAwKSBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzcwXHVjOGZjXHViYmZjXHVjNzU4IFx1Yzc3NFx1Yjk4NFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1Yjk4NFx1Yzc0MCAxLDAwMCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQ1ODlcdWMxMzEgWDNcdWM3NTggXHVhYzAwXHVjZTU4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODMwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiWDMiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGhhcyByZWNlbnRseSBiZWVuIHZpc2l0ZWQgYnkgZXh0cmF0ZXJyZXN0cmlhbHMgZnJvbSBwbGFuZXQgWDMsIHdoZXJlIGV2ZXJ5b25lJnJzcXVvO3MgbmFtZSBpcyBhIHBvc2l0aXZlIGludGVnZXIuIEFsbCByZXNpZGVudHMgb2YgdGhlIHBsYW5ldCBrbm93IGVhY2ggb3RoZXIuIFR3byBYMy1pYW5zIGNhbGN1bGF0ZSB0aGUgc3RyZW5ndGggb2YgdGhlaXIgZnJpZW5kc2hpcCBieSBjb252ZXJ0aW5nIHRoZWlyIG5hbWVzIHRvIGJpbmFyeSwgYWxpZ25pbmcgdGhlbSBvbmUgdW5kZXIgdGhlIG90aGVyLCBhbmQgd3JpdGluZyBhIGRpZ2l0IGluIGVhY2ggY29sdW1uOiAwIGlmIHRoZSB0d28gYmluYXJ5IGRpZ2l0cyBpbiB0aGF0IGNvbHVtbiBhcmUgZXF1YWwsIDEgaWYgdGhleSBkaWZmZXIuIFRoZSBiaW5hcnkgcmVzdWx0IGlzIHRoZW4gY29udmVydGVkIGJhY2sgdG8gdGhlIGRlY2ltYWwgc3lzdGVtLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgdGhlIGZyaWVuZHNoaXAgdmFsdWUgb2YgMTkgYW5kIDEwIGVxdWFscyAyNTo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC94My5wbmdcIiBzdHlsZT1cImhlaWdodDo2OXB4OyB3aWR0aDoxODZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5UaGUgdmFsdWUgb2YgYSBwbGFuZXQgaW4gdGhlIFVuaXZlcnNlIGlzIGRlZmluZWQgYXMgdGhlIHN1bSBvZiBhbGwgZnJpZW5kc2hpcCB2YWx1ZXMuIE1pcmtvIGhhcyBhc2tlZCB5b3UgdG8gaGVscCBoaW0gY29tcHV0ZSB0aGUgdmFsdWUgb2YgcGxhbmV0IFgzISZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHBvc2l0aXZlIGludGVnZXIgTiAodGhlIG51bWJlciBvZiByZXNpZGVudHMgb2YgcGxhbmV0IFgzLCAxICZsZTsgTiAmbGU7IDEgMDAwIDAwMCkuIFRoZSBuZXh0IE4gbGluZXMgY29udGFpbiB0aGUgbmFtZXMgb2YgcmVzaWRlbnRzIC0gcG9zaXRpdmUgaW50ZWdlcnMgc21hbGxlciB0aGFuIDEgMDAwIDAwMCwgb25lIHBlciBsaW5lLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgdmFsdWUgb2YgcGxhbmV0IFgzLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=