Just changing one when the reason for the old one's demise is obvious takes me about 10 minutes. Sometimes finding and dealing with the culprit can more than double that though.
I dealt with a p thing yesterday and it took me nearly 15 minutes to find the piece of thorn (length = tyre thickness) which had done the dirty deed on me.