PROJECT EULER #62

Link to Project Euler problem 62

The cube, 41063625 (345³), can be permuted to produce two other cubes: 56623104 (384³) and 66430125 (405³). In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube.
Find the smallest cube for which exactly five permutations of its digits are cube.

using System;
using System.Collections.Generic;

namespace ProjectEuler
{
    class Program
    {
        static void Main()
        {
            //Problem 62
            DateTime start = DateTime.Now;

            bool success = false;
            Dictionary<int, string> sortedStrings = new Dictionary<int, string>();

            for (int i = 5000; i < 10000; i++)
            {
                BigInt cube = new BigInt(i);
                cube *= i * i;
                char[] c = cube.ToString().ToCharArray();
                Array.Sort(c);
                string s = new string(c);
                if (s.StartsWith("-"))
                    s.Remove(0, 1);
                sortedStrings.Add(i, s);
            }
            for (int i = 5000; i < 9999; i++)
            {
                string s;
                sortedStrings.TryGetValue(i, out s);
                int[] allCubes = new int[5];
                allCubes[0] = i;
                int count = 1;
                for (int j = i + 1; j < 10000; j++)
                {
                    string t;
                    sortedStrings.TryGetValue(j, out t);
                    if (s == t)
                    {
                        count++;
                        allCubes[count - 1] = j;
                    }
                    if (count == 5)
                    {
                        for (int k = 0; k < 5; k++)
                        {
                            int n = allCubes[k];
                            BigInt number = new BigInt(n);
                            number *= n*n;
                            Console.WriteLine(allCubes[k]);
                            Console.WriteLine(number);
                        }
                        Console.WriteLine();
                        success = true;
                        break;
                    }
                }
                if (success) break;
            }
            TimeSpan time = DateTime.Now - start;
            Console.WriteLine("This took {0}", time);
            Console.ReadKey();
        }
    }
}

Triple-click for answer: 127035954683