Largest Prime Removing Digits From Left-Hand End

Recently on Fermat's Library in Twitter, the following curiosity was posted:

What if we tried the same but from the left-hand end? For example, "113" would be a candidate because:

113 is prime
  13 is prime
    3 is prime

What's the largest of such a value? Is the a max one? Well let's leave the digit "zero" aside for now since we're looking to have unique numbers at each step of the sequence.
There is actually a Max value for that! Here it is:

357686312646216567629137

Code to find it is down below - it uses BigInteger and Miller-Rabin for quick primality test. Also, DFS with pruning. Equally interesting as the twitter post. Cheers, ACC.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace FermatLibraryProblem
{
    class Program
    {
        static void Main(string[] args)
        {
            BigInteger max = 0;
            Process(0, 1, ref max);
            Console.WriteLine();
            Console.WriteLine("Solution: {0}", max);
        }

        public static void Process(BigInteger number, BigInteger multiplier, ref BigInteger max)
        {
            if (number != 0 && !IsPrimeMillerRabin(number)) return;

            if (number > max)
            {
                max = number;
                Console.WriteLine("New Max: {0}", max);
            }

            for (int i = 1; i < 10; i++)
            {
                Process(multiplier * i + number, 10 * multiplier, ref max);
            }
        }

        public static bool IsPrimeMillerRabin(BigInteger n)
        {
            //It does not work well for smaller numbers, hence this check
            int SMALL_NUMBER = 1000;

            if (n <= SMALL_NUMBER)
            {
                return IsPrime(n);
            }

            int MAX_WITNESS = 500;
            for (long i = 2; i <= MAX_WITNESS; i++)
            {
                if (IsPrime(i) && Witness(i, n) == 1)
                {
                    return false;
                }
            }

            return true;
        }

        public static BigInteger SqRtN(BigInteger N)
        {
            /*++
             *  Using Newton Raphson method we calculate the
             *  square root (N/g + g)/2
             */
            BigInteger rootN = N;
            int count = 0;
            int bitLength = 1;
            while (rootN / 2 != 0)
            {
                rootN /= 2;
                bitLength++;
            }
            bitLength = (bitLength + 1) / 2;
            rootN = N >> bitLength;

            BigInteger lastRoot = BigInteger.Zero;
            do
            {
                if (lastRoot > rootN)
                {
                    if (count++ > 1000)                   // Work around for the bug where it gets into an infinite loop
                    {
                        return rootN;
                    }
                }
                lastRoot = rootN;
                rootN = (BigInteger.Divide(N, rootN) + rootN) >> 1;
            }
            while (!((rootN ^ lastRoot).ToString() == "0"));
            return rootN;
        }

        public static bool IsPrime(BigInteger n)
        {
            if (n <= 1)
            {
                return false;
            }

            if (n == 2)
            {
                return true;
            }

            if (n % 2 == 0)
            {
                return false;
            }

            for (int i = 3; i <= SqRtN(n) + 1; i += 2)
            {
                if (n % i == 0)
                {
                    return false;
                }
            }
            return true;
        }

        private static int Witness(long a, BigInteger n)
        {
            BigInteger t, u;
            BigInteger prev, curr = 0;
            BigInteger i;
            BigInteger lln = n;

            u = n / 2;
            t = 1;
            while (u % 2 == 0)
            {
                u /= 2;
                t++;
            }

            prev = BigInteger.ModPow(a, u, n);
            for (i = 1; i <= t; i++)
            {
                curr = BigInteger.ModPow(prev, 2, lln);
                if ((curr == 1) && (prev != 1) && (prev != lln - 1)) return 1;
                prev = curr;
            }
            if (curr != 1) return 1;
            return 0;
        }
    }
}