History for query replace pairs

[Tom]

query-replace has a nice feature offering the previous
search/replacement pair as a default, to quickly repeat
the previous search/replace. I find it quite useful.

Often it would also be useful to quickly retrieve
other previous search/replacement pairs. I know I can
select them separately by selecting first the search string 
from the history and then the replacement, but I find
that in most cases I want to use the same replacement which
I used previously for that search.

So a search/replacement pairs history would be quite useful,
it may even be more useful (more frequently used) and 
more convenient than the current history if it were available.

The question is: how could it be integrated into the current
query-replace interface, that is how could the user choose
from a history of defaults (if he does not want to choose the 
latest default which he can access with RET).