Time Limit Check

Time limit2sMemory limit256 MB

Summary

For each case, evaluate f(N) times T from the named complexity and print TLE when it exceeds 10^8 times L.

Level: Easy2 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

Yubin got a time limit exceeded verdict on the judge, and decided to work out the time complexity by hand.

The judge performs $10^8$ operations per second. With a time limit of $L$ seconds it allows $10^8 \times L$ operations in total.

Suppose a program has time complexity $f(N)$ , the input size is at most $N$ , and there are $T$ test cases. The program then performs $f(N) \times T$ operations. If that number is greater than the allowed number of operations, the program exceeds the time limit. Otherwise it may pass.

Report the verdict for each situation.

Input

The first line contains the number of situations $C$ . ( $1 \le C \le 100$ )

Each of the next $C$ lines contains a string $S$ describing the time complexity, the maximum input size $N$ , the number of test cases $T$ , and the time limit $L$ in seconds, separated by spaces. ( $1 \le N \le 10^6$ , $1 \le T \le 10$ , $1 \le L \le 10$ , and $N$ , $T$ , $L$ are integers)

$S$ is one of the following five strings, written without spaces.

O(N): $f(N) = N$
O(N^2): $f(N) = N^2$
O(N^3): $f(N) = N^3$
O(2^N): $f(N) = 2^N$
O(N!): $f(N) = N!$

Output

Print one line per situation. Print TLE! if the program exceeds the time limit, and May Pass. otherwise.

Examples4

Example 1

Input

5
O(N) 1000 10 10
O(2^N) 1000 10 10
O(N!) 2 10 10
O(N^3) 1000 1 10
O(N^3) 1001 1 10

Expected output

May Pass.
TLE!
May Pass.
May Pass.
TLE!

Example 2

Input

5
O(N) 1 1 1
O(N^2) 1 1 1
O(N^3) 1 1 1
O(2^N) 1 1 1
O(N!) 1 1 1

Expected output

May Pass.
May Pass.
May Pass.
May Pass.
May Pass.

Example 3

Input

4
O(N^2) 10000 1 1
O(N^2) 10001 1 1
O(N) 1000000 10 1
O(N^2) 1000000 10 10

Expected output

May Pass.
TLE!
May Pass.
TLE!

Example 4

Input

4
O(N!) 12 1 10
O(N!) 13 1 10
O(2^N) 29 1 10
O(2^N) 30 1 10

Expected output

May Pass.
TLE!
May Pass.
TLE!