You are given a railway seat number as an integer, your task is to check whether it is a valid seat number or not. Also print its berth type i.e lower berth, middle berth, upper berth, side lower berth, side upper berth.

Example Of Train Berth Coach

Input Format:

The first line contains an Integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.
The first and the only line of input of each test case contains an integer, as described in the task.

Output format :

For each test case, the first and the only line of output prints the Birth type if valid otherwise prints "Invalid".
Birth types if valid are "Lower", "Middle", "Upper", "Side Lower" and "Side Upper".

Note:

The output of every test case is printed in a separate line.
You are not required to print anything explicitly. It has already been taken care of.

Constraints:

1 <= T <= 20
1 <= N <= 100

where N is the input berth seat number.