Polski SPOJ i zadanie z liczbami pierwszymi

Witam.
Tu przesyłam zadanie do liczb pierwszych. Poniżej kod. Wywołuję do i analizuję i moim zdaniem zwraca dobrze dane jednak sędzia na SPOJ go odrzuca. Wywołanie trwa mniej niż sekundę. Ktoś ma jakiś pomysł co jest nie tak?

http://pl.spoj.com/problems/PRIME_T/

public static void Main()
        {
            Console.WriteLine("Podaj liczbę przypadków: ");
            int liczbaPrzypadków = int.Parse(Console.ReadLine());
            int modulo = 0;

            for (int i = 1; i <= liczbaPrzypadków; i++)
            {
                Console.WriteLine("Podaj liczbę: ");
                int liczba = int.Parse(Console.ReadLine());

                int countDiv = 0;

                if(liczba%2 == 0 && liczba > 2)
                {
                    Console.WriteLine("NIE");
                }
                else if (liczba % 3 == 0 && liczba > 3)
                {
                    Console.WriteLine("NIE");
                }
                else if (liczba % 5 == 0 && liczba > 5)
                {
                    Console.WriteLine("NIE");
                }
                else if (liczba % 9 == 0 && liczba > 9)
                {
                    Console.WriteLine("NIE");
                }
                else
                {
                    for (int j = 1; j <= liczba; j++)
                    {
                        modulo = liczba % j;

                        if (modulo == 0)
                            countDiv++;
                    }
                    if ((modulo == 0 && i > 1 && i < liczba) || liczba == 1)
                        Console.WriteLine("NIE");
                    else
                        Console.WriteLine("TAK");
                }  
            }
        }  

Treść zadania: Output: Dla każdej liczby słowo TAK, jeśli liczba ta jest pierwsza, słowo: NIE, w przeciwnym wypadku.

Twój kod:

Console.WriteLine("Podaj liczbę przypadków: ");
// ...
Console.WriteLine("Podaj liczbę: ");

BTW ciężko jest mniej wydajnie rozwiązać to zadanie.

Po co ten if z 9, wszystko co jest podzielne przez 9, jest też podzielne przez 3 (które sprawdzasz wcześniej). Tak więc nigdy ci nie "zaskoczy". Gdybyś chciał robić to tak jak robisz z 2, 3, oraz 5, potrzebował byś 25 if-ów. Albo jednego zrobionego z głową, wtedy było by to wydajne rozwiązanie.

if ((modulo == 0 && i > 1 && i < liczba) || liczba == 1)

Co to w ogóle sprawdza? Mam wrażenie, że i znaczy jedynie numer testu, więce nie rozumiem jak się to ma do rzeczy.