Compare elements of same string array quickly

EDIT : I think the C# compiler or something was wrong on the website, I don't know how I could make it any faster than I finally got the project. I switched to Java and it worked fine, exact same logic as the C# project.

using System;

namespace ConsoleApp1
{
class Program
{
    static void Main(string[] args)
    {
        int testCases = int.Parse(Console.ReadLine());
        while (testCases > 0)
        {
            int nNum = int.Parse(Console.ReadLine()); //Needed num version for validation
            string[] numbers = new string[nNum];
            for (int j = 0; j < numbers.Length; j++)               
                numbers[j] = Console.ReadLine(); //This fills array with numbers                
            Array.Sort(numbers); //Sorts string array
            bool consistent = true; //Checking whether we detect any 'inconsistencies'
            for (int j = 0; j < numbers.Length - 1; j++)
            {
                if (numbers[j+1].StartsWith(numbers[j]))
                {
                    consistent = false;
                    break;
                }
                
            }
            Console.WriteLine(consistent ? "YES" : "NO");
            testCases--;
        }

    }
}
}

This is my final code for C#. It just kept going above 3 seconds no matter what I did.

ORIGINAL QUESTION: I'm gonna make it quick -- I've got this task where I get between 1-10000 unique phone numbers. I have to check whether a number within the array is a prefix of another number i.e. '911', is one phone number, and '911859285' is another number, although, I must print that it "isn't a consistent list" due to the prefix of the second number being the first number.

My original idea was a nested for loop... you can see how this is an absolutely terrible idea considering I'd then have to test 100 million comparisons. I tried a bool to break out of this nested loop, but then realised that if indeed all numbers are valid then we've still got the problem.

tl;dr - I need a fast way to compare elements in a string array of 1-10000 elements. If one string is the start of another then it's an invalid list of numbers.

I've seen a bunch of different things like SequenceEquals and LINQ expressions around but I decided to come here for specialised help.

Updated Code

using System;

namespace ConsoleApp1
{
    class Program
    {
    static void Main(string[] args)
    {
        bool validTestNum = false;
        int testCases = 0;
        try
        {
            testCases = int.Parse(Console.ReadLine());
            validTestNum = true;
            if (testCases < 1 || testCases > 40)
            {
                validTestNum = false;
            }
        }
        catch { }

        for (int i = 0; i < testCases; i++)
        {
            bool validN = false;
            string nString = ""; //Needed string 
            int nNum = 0; //Needed num version for validation
            while (!validN)
            {
                nNum = int.Parse(Console.ReadLine());
                validN = true;
                if (nNum < 1 || nNum > 10000)
                    validN = false; //This is validating the amount of phone numbers received
            }

            nString = nNum.ToString();
            string[] numbers = new string[int.Parse(nString)];
            for (int j = 0; j < numbers.Length; j++)
            {
                numbers[j] = Console.ReadLine(); //This fills array with numbers
            }

            bool consistent = true; //Checking whether we detect any 'inconsistencies'
            Array.Sort(numbers); //Sorts string array

            for (int j = 1; j < numbers.Length; j++)
            {
                string possiblePrefix = numbers[j - 1];
                if (j < numbers.Length && numbers[j].StartsWith(possiblePrefix))
                {
                    consistent = false;
                    break;
                }
            }

            if (consistent)
            {
                Console.WriteLine("YES"); //Means the list is consistent
            }
            else if (!consistent)
            {
                Console.WriteLine("NO"); //Means it isn't
            }
        }
        Console.ReadLine();

    }
}

}

Solution

Sort the array. A shorter number like '911' will always precede any longer number it is part of. Example of sorted list:

So, all you have to do is to check whether a given number is the start of the next ones. You can stop as soon as it is not.

Array.Sort(a);
for (int i = 1; i < a.Length; i++) { // Note: we start at index 1, not 0
    string possiblePrefix = a[i - 1];
    for (int k = i; k < a.Length && a[k].StartsWith(possiblePrefix); k++) {
        // a[k] is inconsistent with possiblePrefix , add it to a list or whatever.
        Console.WriteLine($"{possiblePrefix} - {a[k]}");
    }
}

Note that the inner loop will not even start looping for most numbers. Only in the rare cases where inconsistencies are found it will loop. So, this is a near O(n) algorithm. Sorting is a O(n log(n)) operation.

You can also replace the inner loop by a simple if, if you need to know only the first inconsistency of a series.