Transposition

A Transposition Error is when two letters are swapped, such as in "hte" instead of "the", or "rign" instead of "ring".

Given a string of characters, can you fix every place where "gn" appears so it becomes "ng" instead? If there are multiple "g"s in a row, the "n" should be swapped with the first "g". No "gn" should appear in the final text, so be careful with all possibilities!

Full Credit
Try to solve this challenge with only one pass through the text.

I/O Format
The first line of input contains t, the number of tests cases. t lines follow, which each contain a line of text. Output the correctly transposed line of text.