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 $

    Discussion

    Statistics


    86% Solution Ratio

    emrul_muEarliest, Apr '18

    Tarik.amtolyFastest, 0.0s

    atiq_143Lightest, 0 B

    raselrokyShortest, 181B

    Submit

    Login to submit

    Related Contests

    Cybernauts NPC 2018 Ended at 2018-03-24 09:45:00 +0000 UTC
    Replay of Cybernauts NPC 2018 Ended at 2018-04-21 19:00:00 +0000 UTC