Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem J: Forever97与寄信

Problem J: Forever97与寄信

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 233  Solved: 25
[Submit][Status][Web Board]

Description

Forever97与未央是一对笔友,他们经常互相写信。有一天Forever97去邮局寄信,发现邮局的收费方式变成了按字收费,收取的费用为总字数除了其自身以外的最大因子。虽然Forever97是一个有情调的人,但他不想因新收费方式而破财,所以他打算把信分成几份寄出去来减少邮费。已知Forever97写的信共有n个字,可以拆成无数封信,也可以不拆,每封信最少为2个字。求Forever97最少需要付多少邮费?

Input

第一行一个正整数T(T<=200),表示共有T组数据。

2至第T+1行每行一个正整数n(2<=n<=108)

Output

对每组数据输出一行,即Forever97最少需要付的邮费。

Sample Input

3
5
6
9

Sample Output

1
2
2

HINT



对于第二组数据,一封6字信可以拆分成两封3字信,各付1邮资。


对于第三组数据,一封9字信可以拆分成一封2字信和一封7字信,各付1邮资。


[Submit][Status][Web Board]