1. 

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: Problem A - An Industrial Spy
* Link: http://uva.onlinejudge.org/contests/240-0682ae4a/p0.html
*
* @author Dennis Wilfert
* @version 1.0, 11/17/2009
*
* Status : Accepted
* Runtime: 0,92s user 0,05s system
*/
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashSet;

class Main {

// Anzahl der Primzahlen
int erg;

public static void main(String[] args) throws IOException {

new Main().findPrim();
}

void findPrim() throws IOException {

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
PrintWriter writer = new PrintWriter(new BufferedOutputStream(System.out));

// Anzahl der Testfälle
int cases = Integer.parseInt(reader.readLine().trim());
// Arrey mit den einzelnen Ziffern der Zahl
int[] number;
char[] chr;

// Primzahlen berechnen
generatePrimes();

while (cases > 0) {

// Chars in zahl umwandeln
chr = reader.readLine().trim().toCharArray();
number = new int[chr.length];
for (int i = 0; i < chr.length; i++) {
number[i] = chr[i] - 48;
}

// Kopie der Zahl
numclone = number.clone();


numbers2 = new HashSet<Integer>();


erg = 0;
for (int k = number.length; k > 0; k--) {
generate(number, 0, 0, k, number.length);
}
writer.println(erg);


cases--;
}
writer.flush();
}
/*
* Für alle verschiedenen Zahlenkombinationen Prüfen ob summand + summand = summe
*/
// Position im romanchars-Array
int num;
// Summe von s1
int s1sum;
// Summe von s2
int s2sum;
// Summe der Summe
int sumsum;
// Multiplikator
int mult;

/**
* Alle Permutatione berechnen
*/
public void combinations(int[] a, int n, int k) {
// Ist k == 0 kann geprüft werden ob es sich um eine Primzahl handelt
if (k == 0) {
int number = a[0];
for (int i = 1; i < a.length; i++) {
number *= 10;
number += a[i];
}

if (!numbers2.contains(number) && numbers[number] != -1) {
erg++;
numbers2.add(number);
}
}
// Solange i<n Werte vertauschen und die Funktion combinations mit reduziertem n und k wieder aufrufen
for (int i = 0; i < n; i++) {
swap(a, i, n - 1);
combinations(a, n - 1, k - 1);
swap(a, i, n - 1);
}
}
/*
* Werte im Array an den Positionen i und j vertauschen
*/

public void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// Calculate all prime numbers in the range 1 to MAX_PRIME
// using the sieve of Eratosthenes.
// numbers in the "numbers" array that are not prime are are set to -1.
static final int MAX_PRIME = 10000000;
static int[] numbers = new int[MAX_PRIME + 5];
static HashSet<Integer> numbers2;

private void generatePrimes() {
numbers[0] = -1;
numbers[1] = -1;
for (int i = 2; i <= MAX_PRIME + 1; i++) {
if (numbers[i] >= 0) {
numbers[i] = i;
for (int k = 2; k * i <= MAX_PRIME + 1; k++) {
numbers[k * i] = -1;
}
}
}
}
int[] numclone;

private void showCombination(int[] s, int k) {
int[] b = Arrays.copyOf(s, k);
combinations(b, b.length, b.length - 1);
}

public void generate(int[] s, int position, int nextInt, int k, int N) {
if (position == k) {
showCombination(s, k);
return;
}
for (int i = nextInt; i < N; i++) {
s[position] = numclone[i];
generate(s, position + 1, i + 1, k, N);
}
}
}


2.


/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: Problem A - An Industrial Spy
* Link: http://uva.onlinejudge.org/contests/240-0682ae4a/p0.html
*
* @author Christoph Hausmann
* @version 1.0, 12/09/2009
*
* Status : Accepted
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;


public class IndustrialSpy {

public static void main(String... args) throws NumberFormatException, IOException {
final boolean[] noPrimes = computePrimes(10000000); // tells whether number at index i is not a prime (true), or is a prime (false)

noPrimes[1] = true;

final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

for(int numTests = Integer.parseInt(br.readLine()); numTests > 0; numTests--) {
final String curNum = br.readLine();
final char[] numChars = curNum.toCharArray();

final Set<String> set = new HashSet<String>();

for(int i = 0; i < faculty(numChars.length); i++) {
final char[] newNum = permutate(Arrays.copyOf(numChars, numChars.length), i);

for(int strikeCount = 0; strikeCount < newNum.length; strikeCount++) {

final char[] strikeNum = new char[newNum.length-strikeCount];

int pos = 0;

for(int startStrikePos = 0; startStrikePos < newNum.length-strikeCount; startStrikePos++) {
for(int j = 0; j < curNum.length() && pos < strikeNum.length; j++) {
if(strikeCount > 0 && j >= startStrikePos && j < startStrikePos+strikeCount) {
// strike out
} else {
strikeNum[pos] = newNum[j];
pos++;
}
}
}

String s = new String(strikeNum);

while(s.startsWith("0"))
s = s.replaceFirst("0", "");

if(s.length() > 0 && !noPrimes[Integer.parseInt(s)]) {
set.add(s);
}
}



}

System.out.println(set.size());
}
}

private static int faculty(int length) {
int fac = 1;
for(int i = 1; i <= length; i++) {
fac*=i;
}

return fac;
}

private static boolean[] computePrimes(int n) {

final boolean[] noPrimes = new boolean[n];

Arrays.fill(noPrimes, false);

for(int i = 2; i*i <= n; i++) {
if(!noPrimes[i]) {
for(int j = i*i; j < n; j+=i) {
noPrimes[j] = true;
}
}
}

return noPrimes;
}

private static char[] permutate(char[] s, int k) {

for(int j = 1; j <= s.length; j++) {
char temp = s[(k%j)];
s[(k%j)] = s[j-1];
s[j-1] = temp;
k = k / j;
}

return s;
}
}