using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
    static void Main(String[] args) {
        int nQueries = Int32.Parse(Console.ReadLine());

        for(int i = 0; i < nQueries; i++)
        {
            int n = Int32.Parse(Console.ReadLine());

            var queue = new Queue<Node>();
            queue.Enqueue(new Node(n));

            while(queue.Any())
            {
                Node current = queue.Dequeue();

                if(current.Value <= 4)
                {
                    if(current.Value == 4)
                        Console.WriteLine(current.Depth + 3);
                    else
                        Console.WriteLine(current.Depth + current.Value);

                    break;
                }
                
                queue.Enqueue(new Node(current.Value - 1, current.Depth + 1));

                int start = (int)Math.Sqrt(current.Value);
                for(int j = start; j >= 2; j--)
                {
                    if(current.Value % j == 0)
                        queue.Enqueue(new Node(current.Value / j, current.Depth + 1));
                }
            }
        }
    }
}

struct Node
{
    public int Value;
    public int Depth;

    public Node(int value)
    {
        Value = value;
        Depth = 0;
    }

    public Node(int value, int depth)
    {
        Value = value;
        Depth = depth;
    }
}