How to test potentially complicated internals of a class?

OriginalIdeaFoo.cs

// Pretend more profound implementation, where the privates are actually involved and complicated.

public class Foo
{
  public object DoThing()
  {
    return DoAPartOfThing();
  }
  
  public object UndoThing()
  {
    return DoAPartOfThing();
  }
  
  protected object DoAPartOfThing()
  {
    object answer;
  
    for (int i = 0; i < 20; i++)
    {
        // pretend i'm doing something with this
        var result = DoAnotherPartOfThing(i);
    }
    
    return answer;
  }
  
  protected object DoAnotherPartOfThing(int i)
  {
    int result = 0;
    return result;
  }
}

// Going with a "TestFoo" would allow me to test DoAnotherPartOfThing in isolation, but it falls apart with DoAPartOfThing, 
// as it relies on DoAnotherPartOfThing.  If i were to mark the methods as virtual here, it doesn't matter because I need to be able to mock
// the private implementation from Foo, as calling TestFoo.DoAPartOfThing, calls Foo.DoAPartOfThing which in 
// turn calls DoAPartOfThing.DoAnotherPartOfThing

public class TestFoo
{
  public object DoThing()
  {
    throw new NotImplementatedException();
  }
  
  public object UndoThing()
  {
    throw new NotImplementatedException();
  }
  
  public new object DoAPartOfThing()
  {
    return base.DoAPartOfThing();
  }
  
  public new DoAnotherPartOfThing(int i)
  {
    return base.DoAnotherPartOfThing(int i);
  }
}

RefactoredFoo.cs

// Pretend more profound implementation, where the privates are actually involved and complicated.

public class Foo
{

  private readonly _iFooInternals;

  public Foo(IFooInternals iFooInternals)
  {
    _iFooInternals = iFooInternals;
  }

  public object DoThing()
  {
    return DoAPartOfThing();
  }
  
  public object UndoThing()
  {
    return DoAPartOfThing();
  }
  
  protected object DoAPartOfThing()
  {
    return _iFooInternals.DoAPartOfThing();
  }
  
  protected object DoAnotherPartOfThing(int i)
  {
    return _iFooInternals.DoAnotherPartOfThing(i);
  }
}

public interface IFooInternals
{
  object DoAPartOfThing();
  object DoAnotherPartOfThing(int i);
}

public class FooInternals : IFooInternals
{
  public virtual object DoAPartOfThing()
  {
    object answer;
  
    for (int i = 0; i < 20; i++)
    {
        // pretend i'm doing something with this
        var result = DoAnotherPartOfThing(i);
    }
    
    return answer;
  }
  
  public virtual object DoAnotherPartOfThing(int i)
  {
    int result = 0;
    return result;
  }
}