# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Just Primes II (Easy)

By ridowan007 · Limits 3s, 1.0 GB

Given a positive integer N, calculate the minimum number of distinct primes required such that their sum equals to N.

## Input

The first line contains an integer T (1 ≤ T ≤ 50), denoting the number of test cases. Each of the next T lines contains a single integer N (1 ≤ N ≤ 50).

## Output

For each test case, output one integer X. X denotes the minimum number of distinct primes required such that their summation equals to N. If it is not possible to express N as a summation of distinct primes, set X to -1 and output it.

## Sample

InputOutput
```4
1
2
10
27
```
```-1
1
2
3
```

When N = 10, the minimum number of distinct primes is 2 and there is only 1 way to represent 10 as a sum of 2 different prime numbers:

`\$ 3 + 7 = 10 \$`

When N = 27, the minimum number of distinct primes is 3:

`\$ 3 + 5 + 19 = 27 \$`

### Statistics

86% Solution Ratio

emrul_muEarliest, Apr '18

Tarik.amtolyFastest, 0.0s

atiq_143Lightest, 0 B

raselrokyShortest, 181B