Emacs Replace Carriage Return for Line Feed

I recently got a file from a main frame with some crazy use of line feeds and carriage return, thanks to this blog it became really easy. It comes down to replace Carriage Return (if by itself will be shown as a ^M) for Line Feed (which is the same as a ^J). The problem is getting emacs to replace one non-printable character for another. As it turns out C-q lets you type in a linefeed (C-j) as a quoted character. The final steps were:

• M-% [Search and Replace]
• C-q C-m [search for quoted character ^M (carriage return)]
• C-q C-j [replace with quoted character ^J (line feed)]
• ! [replace all]