Forever97与寄信
题号:NC14609
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 128 M,其他语言256 M
64bit IO Format: %lld

题目描述

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

输入描述:

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

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

输出描述:

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

输入

复制
3
5
6
9

输出

复制
1
2
2

说明

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