McCain's "Cross In The Dirt" Story

I've now heard it countless times. McCain has used what appears to be an intensely personal moment in a prison camp as a reason to vote for him in a campaign ad. As he tells it today, it was the pivotal moment in his struggle to survive in the Hanoi Hilton. And yet, in his first thorough account of his time in captivity, in 1973, the story is absent. The story is also hauntingly like that recounted by Solzhenitsen, as told in Luke Veronis, "The Sign of the Cross":

Leaving his shovel on the ground, he slowly walked to a crude bench and sat down. He knew that at any moment a guard would order him to stand up, and when he failed to respond, the guard would beat him to death, probably with his own shovel. He had seen it happen to other prisoners.

As he waited, head down, he felt a presence. Slowly he looked up and saw a skinny old prisoner squat down beside him. The man said nothing. Instead, he used a stick to trace in the dirt the sign of the Cross. The man then got back up and returned to his work.

As Solzhenitsyn stared at the Cross drawn in the dirt his entire perspective changed.

I have one simple question: when was the first time that McCain told this story?