Reduce to Nil | Practice Problems

Reduce to Nil

★★★★★

0 votes

Algorithms, Easy

Details

Submissions

Discussion

Editorial

Problem

Given, a number A. Perform any of the following two operations on A in each move:

If we take two integers x and y, such that, $A = x \times y$ ( $x != 1, y != 1$ ), then we can modify $A = max(x, y)$ .
Decrease the value of A by 1.

Write a program to find out the minimum number of moves required to reduce A to 0.

Input format

The first line of input contains T, the number of test cases.
Each line of a test case contains an integer A.

Output format

For each test case, print the number of steps required to reduce the number to 0.

Constraints

$1 \le T \le 100$

$1 \le A \le 10^6$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

For the first test case $A = 3$ . The optimal sequence of steps to make it 0 are:
$3 -> 2 -> 1 -> 0$
Hence 3 steps are required to move 3 to 0.
For the second test case $A = 6$ . The optimal sequence of steps is as follows:
$6 -> 3 -> 2 -> 1 -> 0$ .
Hence the answer is 4.