RNUM - Rnumber

no tags 

In this problem your task is to reduce a given number 'N' to a non-positive number in as little moves as possible. The moves allowed are : Given an integer 'N' you can subtract one of its factors (excluding 'N' itself) from 'N' and continue the same process with the resulting number until you reach a non-positive number

Input

First line contains the number of test cases 'T'. 'T' lines follow containing a single integer 'N' 2 <= N < 100,000.

Output

A single integer denoting the minimum number of moves necessary.

Example

 
Input: 
1
10
 
Output: 
5

hide comments
nadstratosfer: 2018-06-17 06:20:41

"Factor" means any divisor here, not just prime factor.

Could be a classical problem. Tough TL for slower languages :/


Added by:.:: Pratik ::.
Date:2010-01-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET