시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 128 MB170685962350.650%

문제

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

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

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

감사합니다.

스파이 드림.

입력

첫째 줄에 테스트 케이스의 개수 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+XHVjNTQ4XHViMTU1XHVkNTU4XHVjMTM4XHVjNjk0LiBcdWM4MDBcdWIyOTQgXHVjMGIwXHVjNWM1IFx1YzJhNFx1ZDMwY1x1Yzc3NFx1Yzc4NVx1YjJjOFx1YjJlNC4gXHVjODAwXHVjNzU4IFx1YzgxNVx1Y2NiNFx1Yjk3YyBcdWM4MDhcdWIzMDAgXHViMmU0XHViOTc4IFx1YzBhY1x1Yjc4Y1x1YzVkMFx1YWM4YyBcdWI5ZDBcdWQ1NThcdWM5YzAgXHViOWQwXHVjNTQ0XHVjOGZjXHVjMTM4XHVjNjk0LjxcL3A+XHJcblxyXG48cD5cdWM4MDBcdWM3NTggXHVhYzAwXHVjN2E1IFx1Y2Q1Y1x1YWRmYyBcdWM3N2NcdWM3NDAgXHVjNzIwXHViYTg1XHVkNTVjIFx1YzIxOFx1ZDU1OSBcdWM1ZjBcdWFkNmNcdWMxOGNcdWM3NTggXHVjZDVjXHVjMmUwIFx1YzVmMFx1YWQ2YyBcdWFjYjBcdWFjZmNcdWI5N2MgXHVkNmQ0XHVjY2QwXHVjNjI0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YzVjOFx1YzJiNVx1YjJjOFx1YjJlNC4gXHVjODAwXHViMjk0IFx1YjllNFx1YzZiMCBcdWM3MjBcdWIyYTVcdWQ1NWMgXHVjMGIwXHVjNWM1IFx1YzJhNFx1ZDMwY1x1Yzc3NFx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzVmMFx1YWQ2YyBcdWFjYjBcdWFjZmNcdWI5N2MgXHVjNWI0XHViODM1XHVjOWMwIFx1YzU0YVx1YWM4YyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YzVjOFx1YzJiNVx1YjJjOFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWM4MWNcdWFjMDAgXHVjNjJjIFx1YWM4M1x1Yzc0NCBcdWJiZjhcdWI5YWMgXHVjNTRjXHVjNTU4XHViMjk0XHVjOWMwIFx1YzVmMFx1YWQ2Y1x1YzE4Y1x1YzVkMFx1YzExY1x1YjI5NCBcdWM1ZjBcdWFkNmMgXHVhY2IwXHVhY2ZjXHViOTdjIFx1YmFhOFx1YjQ1MCBcdWMxMWNcdWI5NTggXHVjODA4XHViMmU4XHVhZTMwXHVjNWQwIFx1YjEyM1x1YzViNFx1YmM4NFx1YjgzOFx1YzJiNVx1YjJjOFx1YjJlNC4gXHVjNWI0XHVjYTU0XHVjMjE4IFx1YzVjNlx1Yzc3NCBcdWM4MDBcdWIyOTQgXHViMjA4XHViYjNjXHVjNzQ0IFx1YmEzOFx1YWUwOFx1YWNlMCBcdWM4ODVcdWM3NzQgXHVjODcwXHVhYzAxXHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWQ2ZDRcdWNjZDBcdWM2NTRcdWMyYjVcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzgwMFx1Yjk3YyBcdWFjZTBcdWM2YTlcdWQ1NWMgXHVjMGFjXHViNzhjXHVjNzQwIFx1YjllNFx1YzZiMCBcdWJiMzRcdWMxMWNcdWM2YjQgXHVjMGFjXHViNzhjXHVjNzg1XHViMmM4XHViMmU0LiBcdWI2MTAsIFx1YzgwMFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzJlNFx1YzIxOFx1Yjk3YyBcdWM2YTlcdWIwYTlcdWQ1NThcdWM5YzAgXHVjNTRhXHVjMmI1XHViMmM4XHViMmU0LiBcdWM1YjRcdWI1YmJcdWFjOGNcdWI0ZTAgXHVjNzc0IFx1Yzg4NVx1Yzc3NFx1Yjk3YyBcdWJhYThcdWI0NTAgXHViY2Y1XHVhZDZjXHVkNTc0XHVhYzAwXHVjNTdjXHVkNTY5XHViMmM4XHViMmU0LiBcdWM3NzQgXHVjNWYwXHVhZDZjXHVjMThjXHVjNzU4IFx1YzVmMFx1YWQ2YyBcdWM4ZmNcdWM4MWNcdWIyOTQgXHViZTYwXHViOTc4IFx1YzE4Y1x1Yzc3OFx1YzIxOCBcdWJkODRcdWQ1NzRcdWM3ODVcdWIyYzhcdWIyZTQuIFx1YzgxY1x1YWMwMCBcdWFjMDBcdWM5YzQgXHVjODg1XHVjNzc0IFx1Yzg3MFx1YWMwMVx1YzVkMFx1YjI5NCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVkNTVjIFx1Yzc5MFx1YjlhY1x1YzUyOVx1YjljYyBcdWM4MDFcdWQ2MDBcdWM4MzggXHVjNzg4XHVjMmI1XHViMmM4XHViMmU0LiBcdWM2ZDBcdWI3OTggXHVjMjJiXHVjNzkwXHVhYzAwIFx1YmI1MFx1YzYwMFx1YjI5NFx1YzljMFx1Yjk3YyBcdWM3OTggXHViYWE4XHViOTc0XHVhY2EwXHVjMmI1XHViMmM4XHViMmU0LiBcdWM4ODVcdWM3NzQgXHVjODcwXHVhYzAxXHVjNWQwIFx1YzRmMFx1YzVlYyBcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHViOTdjIFx1YmNmNFx1YjBiNFx1YjRkY1x1YjliNFx1ZDE0Y1x1YjJjOCwgXHVjODg1XHVjNzc0IFx1Yzg3MFx1YWMwMVx1Yzc0NCBcdWM4MDFcdWM4MDhcdWQ3ODggXHViYzMwXHVjZTU4XHVkNTc0XHVjMTFjIFx1YzE4Y1x1YzIxOFx1YWMwMCBcdWI0MThcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1YmE4NyBcdWFjMWNcdWM3NzRcdWM5YzAgXHVjNTRjXHViODI0XHVjOGZjXHVjMmU0IFx1YzIxOCBcdWM3ODhcdWIwOThcdWM2OTQ/PFwvcD5cclxuXHJcbjxwPlx1YWMxMFx1YzBhY1x1ZDU2OVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMmE0XHVkMzBjXHVjNzc0IFx1YjRkY1x1YjliYy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgYyAmbGU7IDIwMCkgXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWM4ODVcdWM3NzRcdWM4NzBcdWFjMDFcdWM1ZDAgXHVjNGYwXHVjNWVjIFx1Yzc4OFx1YjI5NCBcdWMyMThcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNWM2XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjODg1XHVjNzc0XHVjODcwXHVhYzAxXHVjNzU4IFx1YzIxOFx1YjI5NCBcdWM4MDFcdWM1YjRcdWIzYzQgMVx1YWMxYywgXHViOWNlXHVjNTQ0XHVjNTdjIDdcdWFjMWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1Yzg4NVx1Yzc3NFx1Yzg3MFx1YWMwMVx1Yzc0NCBcdWM4MDFcdWM4MDhcdWQ3ODggXHViYzMwXHVjZTU4XHVkNTc0XHVjMTFjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjMThjXHVjMjE4XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHViYWE4XHViNGUwIFx1Yzg4NVx1Yzc3NCBcdWM4NzBcdWFjMDFcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTU4XHVjOWMwIFx1YzU0YVx1YzU0NFx1YjNjNCBcdWI0MWNcdWIyZTQuICg3XHVhY2ZjIDFcdWM3NzQgXHVjNzg4XHVjNzQ0IFx1YjU0YywgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMThjXHVjMjE4XHViMjk0IDcsIDE3LCA3MVx1Yzc3NFx1YjJlNCkgXHVjODg1XHVjNzc0IFx1Yzg3MFx1YWMwMVx1Yzc0NCBcdWM4MDFcdWM4MDhcdWQ3ODggXHViYzMwXHVjZTU4XHVkNTc0XHVjMTFjIFx1YjljY1x1YjRlMCBcdWMyMmJcdWM3OTBcdWFjMDAgMFx1YzczY1x1Yjg1YyBcdWMyZGNcdWM3OTFcdWQ1NjAgXHViNTRjLCBcdWM1NWVcdWM1ZDBcdWM3ODhcdWIyOTQgMFx1Yzc0NCBcdWM5YzBcdWM2YjQgXHVjMjE4XHVhYzAwIFx1YWMxOVx1YzczY1x1YmE3NCBcdWFjMTlcdWM3NDAgXHVjMjJiXHVjNzkwXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjM2NzEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBbiBJbmR1c3RyaWFsIFNweSIsImRlc2NyaXB0aW9uIjoiPHA+SW5kdXN0cmlhbCBzcHlpbmcgaXMgdmVyeSBjb21tb24gZm9yIG1vZGVybiByZXNlYXJjaCBsYWJzLiBJIGFtIHN1Y2ggYW4gaW5kdXN0cmlhbCBzcHkgLSBkb24mIzM5O3QgdGVsbCBhbnlib2R5ISBNeSByZWNlbnQgam9iIHdhcyB0byBzdGVhbCB0aGUgbGF0ZXN0IGludmVudGlvbnMgZnJvbSBhIGZhbW91cyBtYXRoIHJlc2VhcmNoIGxhYi4gSXQgd2FzIGhhcmQgdG8gb2J0YWluIHNvbWUgb2YgdGhlaXIgcmVzdWx0cyBidXQgSSBnb3QgdGhlaXIgd2FzdGUgb3V0IG9mIGEgZG9jdW1lbnQgc2hyZWRkZXIuPFwvcD5cclxuXHJcbjxwPkkgaGF2ZSBhbHJlYWR5IHJlY29uc3RydWN0ZWQgdGhhdCB0aGVpciByZXNlYXJjaCB0b3BpYyBpcyBmYXN0IGZhY3Rvcml6YXRpb24uIEJ1dCB0aGUgcmVtYWluaW5nIHBhcGVyIHNuaXBwZXRzIG9ubHkgaGF2ZSBzaW5nbGUgZGlnaXRzIG9uIGl0IGFuZCBJIGNhbm5vdCBpbWFnaW5lIHdoYXQgdGhleSBhcmUgZm9yLiBDb3VsZCBpdCBiZSB0aGF0IHRob3NlIGRpZ2l0cyBmb3JtIHByaW1lIG51bWJlcnM/IFBsZWFzZSBoZWxwIG1lIHRvIGZpbmQgb3V0IGhvdyBtYW55IHByaW1lIG51bWJlcnMgY2FuIGJlIGZvcm1lZCB1c2luZyB0aGUgZ2l2ZW4gZGlnaXRzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGhvbGRzIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBjICgxICZsZTsgYyAmbGU7IDIwMCkuIEVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIGEgc2luZ2xlIGxpbmUuIFRoaXMgbGluZSBjb250YWlucyB0aGUgZGlnaXRzIChhdCBsZWFzdCBvbmUsIGF0IG1vc3Qgc2V2ZW4pIHRoYXQgYXJlIG9uIHRoZSBwYXBlciBzbmlwcGV0cy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHByaW50IG9uZSBsaW5lIGNvbnRhaW5pbmcgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgcHJpbWVzIHRoYXQgY2FuIGJlIHJlY29uc3RydWN0ZWQgYnkgc2h1ZmZsaW5nIHRoZSBkaWdpdHMuIFlvdSBtYXkgaWdub3JlIGRpZ2l0cyB3aGlsZSByZWNvbnN0cnVjdGluZyB0aGUgcHJpbWVzIChlLmcuLCBpZiB5b3UgZ2V0IHRoZSBkaWdpdHMgNyBhbmQgMSwgeW91IGNhbiByZWNvbnN0cnVjdCB0aHJlZSBwcmltZXMgNywgMTcsIGFuZCA3MSkuIFJlY29uc3RydWN0ZWQgbnVtYmVycyB0aGF0IChyZWdhcmRlZCBhcyBzdHJpbmdzKSBkaWZmZXIganVzdCBieSBsZWFkaW5nIHplcm9zLCBhcmUgY29uc2lkZXJlZCBpZGVudGljYWwgKHNlZSB0aGUgZm91cnRoIGNhc2Ugb2YgdGhlIHNhbXBsZSBpbnB1dCkuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

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