시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 206 107 88 52.695%

문제

안녕하세요. 저는 산업 스파이입니다. 저의 정체를 절대 다른 사람에게 말하지 말아주세요.

저의 가장 최근 일은 유명한 수학 연구소의 최신 연구 결과를 훔쳐오는 것이었습니다. 저는 매우 유능한 산업 스파이이기 때문에, 연구 결과를 어렵지 않게 얻을 수 있었습니다. 하지만, 제가 올 것을 미리 알았는지 연구소에서는 연구 결과를 모두 서류 절단기에 넣어버렸습니다. 어쩔수 없이 저는 눈물을 머금고 종이 조각을 모두 훔쳐왔습니다.

저를 고용한 사람은 매우 무서운 사람입니다. 또, 저는 프로이기 때문에 실수를 용납하지 않습니다. 어떻게든 이 종이를 모두 복구해가야합니다. 이 연구소의 연구 주제는 빠른 소인수 분해입니다. 제가 가진 종이 조각에는 숫자가 한 자리씩만 적혀져 있습니다. 원래 숫자가 뭐였는지를 잘 모르겠습니다. 종이 조각에 써있는 숫자를 보내드릴테니, 종이 조각을 적절히 배치해서 소수가 되는 경우가 몇 개이지 알려주실 수 있나요?

감사합니다.

스파이 드림.

입력

첫째 줄에 테스트 케이스의 개수 c가 주어진다. (1 ≤ c ≤ 200) 각 테스트 케이스는 한 줄로 이루어져 있고, 종이조각에 써있는 수가 공백없이 주어진다. 종이조각의 수는 적어도 1개, 많아야 7개이다.

출력

각 테스트 케이스에 대해 종이조각을 적절히 배치해서 만들 수 있는 서로 다른 소수의 개수를 출력한다. 이 때, 모든 종이 조각을 사용하지 않아도 된다. (7과 1이 있을 때, 만들 수 있는 소수는 7, 17, 71이다) 종이 조각을 적절히 배치해서 만든 숫자가 0으로 시작할 때, 앞에있는 0을 지운 수가 같으면 같은 숫자이다.

예제 입력 1

4
17
1276543
9999999
011

예제 출력 1

3
1336
0
2
W3sicHJvYmxlbV9pZCI6IjM2NzEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYjBcdWM1YzUgXHVjMmE0XHVkMzBjXHVjNzc0XHVjNzU4IFx1ZDNiOFx1YzljMCIsImRlc2NyaXB0aW9uIjoiPHA+XHJcblx0XHVjNTQ4XHViMTU1XHVkNTU4XHVjMTM4XHVjNjk0LiBcdWM4MDBcdWIyOTQgXHVjMGIwXHVjNWM1IFx1YzJhNFx1ZDMwY1x1Yzc3NFx1Yzc4NVx1YjJjOFx1YjJlNC4gXHVjODAwXHVjNzU4IFx1YzgxNVx1Y2NiNFx1Yjk3YyBcdWM4MDhcdWIzMDAgXHViMmU0XHViOTc4IFx1YzBhY1x1Yjc4Y1x1YzVkMFx1YWM4YyBcdWI5ZDBcdWQ1NThcdWM5YzAgXHViOWQwXHVjNTQ0XHVjOGZjXHVjMTM4XHVjNjk0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM4MDBcdWM3NTggXHVhYzAwXHVjN2E1IFx1Y2Q1Y1x1YWRmYyBcdWM3N2NcdWM3NDAgXHVjNzIwXHViYTg1XHVkNTVjIFx1YzIxOFx1ZDU1OSBcdWM1ZjBcdWFkNmNcdWMxOGNcdWM3NTggXHVjZDVjXHVjMmUwIFx1YzVmMFx1YWQ2YyBcdWFjYjBcdWFjZmNcdWI5N2MgXHVkNmQ0XHVjY2QwXHVjNjI0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YzVjOFx1YzJiNVx1YjJjOFx1YjJlNC4gXHVjODAwXHViMjk0IFx1YjllNFx1YzZiMCBcdWM3MjBcdWIyYTVcdWQ1NWMgXHVjMGIwXHVjNWM1IFx1YzJhNFx1ZDMwY1x1Yzc3NFx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzVmMFx1YWQ2YyBcdWFjYjBcdWFjZmNcdWI5N2MgXHVjNWI0XHViODM1XHVjOWMwIFx1YzU0YVx1YWM4YyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YzVjOFx1YzJiNVx1YjJjOFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWM4MWNcdWFjMDAgXHVjNjJjIFx1YWM4M1x1Yzc0NCBcdWJiZjhcdWI5YWMgXHVjNTRjXHVjNTU4XHViMjk0XHVjOWMwIFx1YzVmMFx1YWQ2Y1x1YzE4Y1x1YzVkMFx1YzExY1x1YjI5NCBcdWM1ZjBcdWFkNmMgXHVhY2IwXHVhY2ZjXHViOTdjIFx1YmFhOFx1YjQ1MCBcdWMxMWNcdWI5NTggXHVjODA4XHViMmU4XHVhZTMwXHVjNWQwIFx1YjEyM1x1YzViNFx1YmM4NFx1YjgzOFx1YzJiNVx1YjJjOFx1YjJlNC4gXHVjNWI0XHVjYTU0XHVjMjE4IFx1YzVjNlx1Yzc3NCBcdWM4MDBcdWIyOTQgXHViMjA4XHViYjNjXHVjNzQ0IFx1YmEzOFx1YWUwOFx1YWNlMCBcdWM4ODVcdWM3NzQgXHVjODcwXHVhYzAxXHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWQ2ZDRcdWNjZDBcdWM2NTRcdWMyYjVcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzgwMFx1Yjk3YyBcdWFjZTBcdWM2YTlcdWQ1NWMgXHVjMGFjXHViNzhjXHVjNzQwIFx1YjllNFx1YzZiMCBcdWJiMzRcdWMxMWNcdWM2YjQgXHVjMGFjXHViNzhjXHVjNzg1XHViMmM4XHViMmU0LiBcdWI2MTAsIFx1YzgwMFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzJlNFx1YzIxOFx1Yjk3YyBcdWM2YTlcdWIwYTlcdWQ1NThcdWM5YzAgXHVjNTRhXHVjMmI1XHViMmM4XHViMmU0LiBcdWM1YjRcdWI1YmJcdWFjOGNcdWI0ZTAgXHVjNzc0IFx1Yzg4NVx1Yzc3NFx1Yjk3YyBcdWJhYThcdWI0NTAgXHViY2Y1XHVhZDZjXHVkNTc0XHVhYzAwXHVjNTdjXHVkNTY5XHViMmM4XHViMmU0LiBcdWM3NzQgXHVjNWYwXHVhZDZjXHVjMThjXHVjNzU4IFx1YzVmMFx1YWQ2YyBcdWM4ZmNcdWM4MWNcdWIyOTQgXHViZTYwXHViOTc4IFx1YzE4Y1x1Yzc3OFx1YzIxOCBcdWJkODRcdWQ1NzRcdWM3ODVcdWIyYzhcdWIyZTQuIFx1YzgxY1x1YWMwMCBcdWFjMDBcdWM5YzQgXHVjODg1XHVjNzc0IFx1Yzg3MFx1YWMwMVx1YzVkMFx1YjI5NCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVkNTVjIFx1Yzc5MFx1YjlhY1x1YzUyOVx1YjljYyBcdWM4MDFcdWQ2MDBcdWM4MzggXHVjNzg4XHVjMmI1XHViMmM4XHViMmU0LiBcdWM2ZDBcdWI3OTggXHVjMjJiXHVjNzkwXHVhYzAwIFx1YmI1MFx1YzYwMFx1YjI5NFx1YzljMFx1Yjk3YyBcdWM3OTggXHViYWE4XHViOTc0XHVhY2EwXHVjMmI1XHViMmM4XHViMmU0LiBcdWM4ODVcdWM3NzQgXHVjODcwXHVhYzAxXHVjNWQwIFx1YzM2OFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWI5N2MgXHViY2Y0XHViMGI0XHViNGRjXHViOWI0XHVkMTRjXHViMmM4LCBcdWM4ODVcdWM3NzQgXHVjODcwXHVhYzAxXHVjNzQ0IFx1YzgwMVx1YzgwOFx1ZDc4OCBcdWJjMzBcdWNlNThcdWQ1NzRcdWMxMWMgXHVjMThjXHVjMjE4XHVhYzAwIFx1YjQxOFx1YjI5NCBcdWFjYmRcdWM2YjBcdWFjMDAgXHViYTg3IFx1YWMxY1x1Yzc3NFx1YzljMCBcdWM1NGNcdWI4MjRcdWM4ZmNcdWMyZTQgXHVjMjE4IFx1Yzc4OFx1YjA5OFx1YzY5ND88XC9wPlxyXG5cclxuPHA+XHJcblx0XHVhYzEwXHVjMGFjXHVkNTY5XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWMyYTRcdWQzMGNcdWM3NzQgXHViNGRjXHViOWJjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBjICZsZTsgMjAwKSBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1Yzg4NVx1Yzc3NFx1Yzg3MFx1YWMwMVx1YzVkMCBcdWMzNjhcdWM3ODhcdWIyOTQgXHVjMjE4XHVhYzAwIFx1YWNmNVx1YmMzMVx1YzVjNlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzg4NVx1Yzc3NFx1Yzg3MFx1YWMwMVx1Yzc1OCBcdWMyMThcdWIyOTQgXHVjODAxXHVjNWI0XHViM2M0IDFcdWFjMWMsIFx1YjljZVx1YzU0NFx1YzU3YyA3XHVhYzFjXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWM4ODVcdWM3NzRcdWM4NzBcdWFjMDFcdWM3NDQgXHVjODAxXHVjODA4XHVkNzg4IFx1YmMzMFx1Y2U1OFx1ZDU3NFx1YzExYyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YzE4Y1x1YzIxOFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWJhYThcdWI0ZTAgXHVjODg1XHVjNzc0IFx1Yzg3MFx1YWMwMVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNTQ0XHViM2M0IFx1YjQxY1x1YjJlNC4gKDdcdWFjZmMgMVx1Yzc3NCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMxOGNcdWMyMThcdWIyOTQgNywgMTcsIDcxXHVjNzc0XHViMmU0KSBcdWM4ODVcdWM3NzQgXHVjODcwXHVhYzAxXHVjNzQ0IFx1YzgwMVx1YzgwOFx1ZDc4OCBcdWJjMzBcdWNlNThcdWQ1NzRcdWMxMWMgXHViOWNjXHViNGUwIFx1YzIyYlx1Yzc5MFx1YWMwMCAwXHVjNzNjXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU2MCBcdWI1NGMsIFx1YzU1ZVx1YzVkMFx1Yzc4OFx1YjI5NCAwXHVjNzQ0IFx1YzljMFx1YzZiNCBcdWMyMThcdWFjMDAgXHVhYzE5XHVjNzNjXHViYTc0IFx1YWMxOVx1Yzc0MCBcdWMyMmJcdWM3OTBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzY3MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkFuIEluZHVzdHJpYWwgU3B5IiwiZGVzY3JpcHRpb24iOiI8cD5JbmR1c3RyaWFsIHNweWluZyBpcyB2ZXJ5IGNvbW1vbiBmb3IgbW9kZXJuIHJlc2VhcmNoIGxhYnMuIEkgYW0gc3VjaCBhbiBpbmR1c3RyaWFsIHNweSAtIGRvbiYjMzk7dCB0ZWxsIGFueWJvZHkhIE15IHJlY2VudCBqb2Igd2FzIHRvIHN0ZWFsIHRoZSBsYXRlc3QgaW52ZW50aW9ucyBmcm9tIGEgZmFtb3VzIG1hdGggcmVzZWFyY2ggbGFiLiBJdCB3YXMgaGFyZCB0byBvYnRhaW4gc29tZSBvZiB0aGVpciByZXN1bHRzIGJ1dCBJIGdvdCB0aGVpciB3YXN0ZSBvdXQgb2YgYSBkb2N1bWVudCBzaHJlZGRlci48XC9wPlxyXG5cclxuPHA+SSBoYXZlIGFscmVhZHkgcmVjb25zdHJ1Y3RlZCB0aGF0IHRoZWlyIHJlc2VhcmNoIHRvcGljIGlzIGZhc3QgZmFjdG9yaXphdGlvbi4gQnV0IHRoZSByZW1haW5pbmcgcGFwZXIgc25pcHBldHMgb25seSBoYXZlIHNpbmdsZSBkaWdpdHMgb24gaXQgYW5kIEkgY2Fubm90IGltYWdpbmUgd2hhdCB0aGV5IGFyZSBmb3IuIENvdWxkIGl0IGJlIHRoYXQgdGhvc2UgZGlnaXRzIGZvcm0gcHJpbWUgbnVtYmVycz8gUGxlYXNlIGhlbHAgbWUgdG8gZmluZCBvdXQgaG93IG1hbnkgcHJpbWUgbnVtYmVycyBjYW4gYmUgZm9ybWVkIHVzaW5nIHRoZSBnaXZlbiBkaWdpdHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgaG9sZHMgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIGMgKDEgJmxlOyBjICZsZTsgMjAwKS4gRWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgYSBzaW5nbGUgbGluZS4gVGhpcyBsaW5lIGNvbnRhaW5zIHRoZSBkaWdpdHMgKGF0IGxlYXN0IG9uZSwgYXQgbW9zdCBzZXZlbikgdGhhdCBhcmUgb24gdGhlIHBhcGVyIHNuaXBwZXRzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgb25lIGxpbmUgY29udGFpbmluZyB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCBwcmltZXMgdGhhdCBjYW4gYmUgcmVjb25zdHJ1Y3RlZCBieSBzaHVmZmxpbmcgdGhlIGRpZ2l0cy4gWW91IG1heSBpZ25vcmUgZGlnaXRzIHdoaWxlIHJlY29uc3RydWN0aW5nIHRoZSBwcmltZXMgKGUuZy4sIGlmIHlvdSBnZXQgdGhlIGRpZ2l0cyA3IGFuZCAxLCB5b3UgY2FuIHJlY29uc3RydWN0IHRocmVlIHByaW1lcyA3LCAxNywgYW5kIDcxKS4gUmVjb25zdHJ1Y3RlZCBudW1iZXJzIHRoYXQgKHJlZ2FyZGVkIGFzIHN0cmluZ3MpIGRpZmZlciBqdXN0IGJ5IGxlYWRpbmcgemVyb3MsIGFyZSBjb25zaWRlcmVkIGlkZW50aWNhbCAoc2VlIHRoZSBmb3VydGggY2FzZSBvZiB0aGUgc2FtcGxlIGlucHV0KS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2009 A번