시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 679 251 202 37.828%

문제

상근이의 할머니는 매우 유명한 수학자이다. 할머니는 매일 수학 문제로 상근이를 힘들게 한다. 할머니는 종이 N장에 숫자를 하나씩 쓴 다음 상근이에게 준다. 그 다음 상근이는 다음과 같이 문제를 풀어야 한다.

두 수 A와 B를 고르고, A를 나눌 수 있는 소수 X를 고른다. 그 다음, A를 지우고 A/X를 쓰고, B를 지우고 B×X를 쓴다.

상근이는 위의 행동을 무한히 반복할 수 있다. 할머니는 상근이가 만든 수를 보고 점수를 계산한다. 점수가 높을수록 할머니는 상근이에게 사탕을 많이 준다. 점수는 종이에 적혀있는 모든 수의 최대공약수이다.

상근이가 얻을 수 있는 가장 높은 점수를 구하는 프로그램을 작성하시오. 또, 그 점수를 얻으려면 최소 몇 번 해야 하는지도 구한다.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100) 둘째 줄에는 종이에 적혀있는 수 N개가 주어진다. 수는 모두 1,000,000보다 작거나 같은 양의 정수이다.

출력

첫째 줄에 상근이가 얻을 수 있는 가장 큰 점수와 최소 몇 번 만에 그 점수를 얻을 수 있는지를 출력한다. 

예제 입력 1

3
8 24 9

예제 출력 1

12 3
W3sicHJvYmxlbV9pZCI6IjI5MDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMThcdWQ1NTlcdWM3NDAgXHViMTA4XHViYjM0IFx1YzI2Y1x1YzZjYyIsImRlc2NyaXB0aW9uIjoiPHA+XHJcblx0XHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1ZDU2MFx1YmEzOFx1YjJjOFx1YjI5NCBcdWI5ZTRcdWM2YjAgXHVjNzIwXHViYTg1XHVkNTVjIFx1YzIxOFx1ZDU1OVx1Yzc5MFx1Yzc3NFx1YjJlNC48c3BhbiBjbGFzcz1cIkFwcGxlLXRhYi1zcGFuXCIgc3R5bGU9XCJ3aGl0ZS1zcGFjZTpwcmVcIj4gPFwvc3Bhbj5cdWQ1NjBcdWJhMzhcdWIyYzhcdWIyOTQgXHViOWU0XHVjNzdjIFx1YzIxOFx1ZDU1OSBcdWJiMzhcdWM4MWNcdWI4NWMgXHVjMGMxXHVhZGZjXHVjNzc0XHViOTdjIFx1ZDc5OFx1YjRlNFx1YWM4YyBcdWQ1NWNcdWIyZTQuIFx1ZDU2MFx1YmEzOFx1YjJjOFx1YjI5NCBcdWM4ODVcdWM3NzQgTlx1YzdhNVx1YzVkMCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzRmNCBcdWIyZTRcdWM3NGMgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNWQwXHVhYzhjIFx1YzkwMFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWJiMzhcdWM4MWNcdWI5N2MgXHVkNDgwXHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViNDUwIFx1YzIxOCBBXHVjNjQwIEJcdWI5N2MgXHVhY2UwXHViOTc0XHVhY2UwLCBBXHViOTdjIFx1YjA5OFx1YjIwYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzE4Y1x1YzIxOCBYXHViOTdjIFx1YWNlMFx1Yjk3OFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YywgQVx1Yjk3YyBcdWM5YzBcdWM2YjBcdWFjZTAgQVwvWFx1Yjk3YyBcdWM0ZjBcdWFjZTAsIEJcdWI5N2MgXHVjOWMwXHVjNmIwXHVhY2UwIEImdGltZXM7WFx1Yjk3YyBcdWM0ZjRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3MDRcdWM3NTggXHVkNTg5XHViM2Q5XHVjNzQ0IFx1YmIzNFx1ZDU1Y1x1ZDc4OCBcdWJjMThcdWJjZjVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNTYwXHViYTM4XHViMmM4XHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWI5Y2NcdWI0ZTAgXHVjMjE4XHViOTdjIFx1YmNmNFx1YWNlMCBcdWM4MTBcdWMyMThcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTVjXHViMmU0LiBcdWM4MTBcdWMyMThcdWFjMDAgXHViMTkyXHVjNzQ0XHVjMjE4XHViODVkIFx1ZDU2MFx1YmEzOFx1YjJjOFx1YjI5NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM1ZDBcdWFjOGMgXHVjMGFjXHVkMGQ1XHVjNzQ0IFx1YjljZVx1Yzc3NCBcdWM5MDBcdWIyZTQuIFx1YzgxMFx1YzIxOFx1YjI5NCBcdWM4ODVcdWM3NzRcdWM1ZDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWMyMThcdWM3NTggXHVjZDVjXHViMzAwXHVhY2Y1XHVjNTdkXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YjE5Mlx1Yzc0MCBcdWM4MTBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YjYxMCwgXHVhZGY4IFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWM1YmJcdWM3M2NcdWI4MjRcdWJhNzQgXHVjZDVjXHVjMThjIFx1YmE4NyBcdWJjODggXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NFx1YzljMFx1YjNjNCBcdWFkNmNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMDApIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODg1XHVjNzc0XHVjNWQwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWMyMTggTlx1YWMxY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzIxOFx1YjI5NCBcdWJhYThcdWI0NTAgMSwwMDAsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YzgxMFx1YzIxOFx1YzY0MCBcdWNkNWNcdWMxOGMgXHViYTg3IFx1YmM4OCBcdWI5Y2NcdWM1ZDAgXHVhZGY4IFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjkwNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IklLUyIsImRlc2NyaXB0aW9uIjoiPHA+TWlya29zIGdyZWF0IGdyYW5kbW90aGVyIEthdGljYSBpcyBhbiBhdmlkIG1hdGhlbWF0aWNpYW4uIFNoZSBsaWtlcyB0byB0b3JtZW50IE1pcmtvIHdpdGggbWF0aCBnYW1lcy4gVGhpcyB0aW1lIHNoZSB3cm90ZSBkb3duIGEgc2VxdWVuY2Ugb2YgbnVtYmVycyBvbiBhIHBpZWNlIG9mIHBhcGVyIGFuZCB0b2xkIE1pcmtvIGhlIG1heSBkbyB0aGUgZm9sbG93aW5nOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkNob29zZSBhbnkgdHdvIG51bWJlcnMgaW4gdGhlIHNlcXVlbmNlIChsZXQmIzM5O3MgY2FsbCB0aGVtIEEgaSBCKSBhbmQgYSBwcmltZSBudW1iZXIgWCBzdWNoIHRoYXQgQSBpcyBkaXZpc2libGUgYnkgWC4gQWZ0ZXIgdGhhdCwgTWlya28gZXJhc2VzIEEgYW5kIHdyaXRlcyBcXChcXGZyYWN7QX17WH1cXCkgaW4gaXRzIHBsYWNlLiBJbiB0aGUgZW5kIGhlIGVyYXNlcyBCIGFuZCB3cml0ZXMgXFwoQiBcXHRpbWVzIFhcXCkgaW4gaXRzIHBsYWNlLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPk1pcmtvIG1heSBwZXJmb3JtIHRoaXMgb3BlcmF0aW9uIGFzIG1hbnkgdGltZXMgaGUgd2FudHMuIEhpcyBnb2FsIGlzIHRvIG9idGFpbiB0aGUgbWF4aW11bSBwb3NzaWJsZSBzY29yZSwgYmVjYXVzZSBoZSBnZXRzIGNhbmR5IGZyb20gaGlzIGdyZWF0IGdyYW5kbW90aGVyIGlmIGhlIGRvZXMgc28uIFRoZSBzY29yZSBmb3Igb25lIHNlcXVlbmNlIGlzIHRoZSBncmVhdGVzdCBjb21tb24gZGl2aXNvciBvZiBhbGwgdGhlIG51bWJlcnMgaW4gdGhlIHNlcXVlbmNlLjxcL3A+XHJcblxyXG48cD5IZSBpcyBub3QgdmVyeSBnb29kIGF0IHRoaXMsIGFuZCBoZSBsaWtlcyBoaXMgY2FuZHkgc28gaGUgaGFzIGFza2VkIHlvdSB0byBoZWxwIGhpbS4gV3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBjYWxjdWxhdGUgdGhlIG1heGltdW0gcG9zc2libGUgc2NvcmUuIFNpbmNlIHlvdSBhcmUgc3VjaCBhIG5pY2UgZ3V5LCB5b3Ugc2hvdWxkIGFsc28gcHJpbnQgdGhlIHNtYWxsZXN0IG51bWJlciBvZiB0aW1lcyBNaXJrbyBtdXN0IHBlcmZvcm0gdGhlIG9wZXJhdGlvbiB0byBvYnRhaW4gdGhlIG1heGltdW0gcG9zc2libGUgc2NvcmUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBvbmUgaW50ZWdlciBOLCAoMSAmbGU7IE4gJmxlOyAxMDApLCBudW1iZXIgb2YgZWxlbWVudHMgaW4gdGhlIHN0YXJ0aW5nIHNlcXVlbmNlLjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgTiBwb3NpdGl2ZSBpbnRlZ2VycyBzbWFsbGVyIHRoYW4gb3IgZXF1YWwgdG8gMSAwMDAgMDAwLCB0aGUgc2VxdWVuY2UgS2F0aWNhIGdhdmUgdG8gTWlya28uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG9uZSBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiB0d28gaW50ZWdlcnMuIFRoZSBmaXJzdCBpbnRlZ2VyIGlzIHRoZSBtYXhpbWFsIHBvc3NpYmxlIHNjb3JlIE1pcmtvIGNhbiBvYnRhaW4uIFRoZSBzZWNvbmQgaW50ZWdlciBpcyB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIG9wZXJhdGlvbnMgTWlya28gbmVlZHMgdG8gcGVyZm9ybSB0byBvYnRhaW4gaXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d