说明

Yokile fell in love with CC at first sight,just like campus movie in Japan.

But Yokile is so shy also he is fear.Meanwhile Yokile know nothing about CC.

Yokile decided to get close her after a period of struggle.

because Yokile wish to see her.

CC tell Yokile she doesn’t believe in love at first sight in campus movie in Japan.

But CC tell Yokile if you solve the problem l will make friend with you.otherwise CC will forgotten all the memories with Yokile

The problem as follow：

now you have a integer n，you should to split the initial n in several parts n1 + n2 + ... + nk = n(here k is arbitrary, even k = 1 is allowed) ，all of ni should be prime number，now want to k is minimum. if no answer you should be print -1

For example 

n = 6,  6 = 2 + 3 so answer = 2

n = 11, because 11 is a prime number, so answer = 1

n = 12, n = 7 + 5, so the answer = 2

Yokile really want to make friend with CC,but Yokile is a fool in love and math aspect

Can you help the Yokile?

输入格式

The first line of the input contains a single integer T (T <= 30)

next T line, each of line contains a integer n (2 <= n <= 2000000000)

输出格式

For each of test you should output one line.The line should contain the answer.

3
6
11
12

2
1
2

来源

Yokile's youth