# Day 25: Running Time and Complexity

## Objective 
Today we're learning about running time! Check out the [Tutorial](https://www.hackerrank.com/challenges/30-running-time-and-complexity/tutorial) tab for learning materials and an instructional video!

### Task 
A *prime* is a natural number greater 1 than  that has no positive divisors other than 1 and itself. Given a number, **n**, determine and print whether it's **Prime** or **Not Prime**.

**Note**: If possible, try to come up with a **_O(sqrt(n))_** primality algorithm, or see what sort of optimizations you come up with for an **_O(n)_** algorithm. Be sure to check out the Editorial after submitting your code!


### Input Format

The first line contains an integer, **_T_**, the number of test cases. 
Each of the **_T_** subsequent lines contains an integer, **_n_**, to be tested for primality.

### Constraints

 - **1 <= T <= 20**
 - **1 <= n <= 2 x 10 <sup>9</sup>**

### Output Format

For each test case, print whether **_n_** is **Prime** or **Not Prime** on a new line.

### Sample Input
```Python
3
12
5
7
```

### Sample Output
```Python
Not prime
Prime
Prime
```