Railway Seat Berth Determination

Given a railway seat number represented as an integer, determine if it is a valid seat number and identify its berth type. Possible berth types include lower berth, middle berth, upper berth, side lower berth, and side upper berth.

Input:

The first line contains an integer 't', representing the number of test cases. Each of the next 't' lines contains one integer representing the railway seat number.

Output:

For each test case, output the berth type if the seat number is valid, otherwise output "Invalid". Possible berth types are "Lower", "Middle", "Upper", "Side Lower", and "Side Upper".

Example:

Input:

t = 2 
 Seat numbers: 25 
 Seat numbers: 38

Output:

Upper 
 Invalid

Constraints:

• 1 <= T <= 20
• 1 <= N <= 100 (where N is the input berth seat number)