The Messy Export

Marlow Freight receives its supplier catalogue as a spreadsheet export, and the export pads values with stray spaces — sometimes in front, sometimes behind, sometimes both. On screen those spaces are invisible, but they are real characters in the file, so alice and alice count as two different suppliers to everything downstream. Spaces sitting inside a value are part of the value and have to survive.

Task: Print each value with its padding removed.

Input

The first line holds one integer n, how many values follow. Each of the next n lines holds one value. A line may be padded in front, behind, on both sides, or on neither. A value may itself contain spaces in the middle.

Output

n lines in the same order, each holding its value with the padding at the two ends removed and everything else left exactly as it was.

Example:

Input:
3
  alice
bob
  carol

Output:
alice
bob
carol