Ярославские ученые открыли задачу оптимизации, которая годами не давала им покоя. И вот, в 2019 году, профессор Р. смог разрешить её, прибегнув к моделированию её решения на компьютере, что далось ему нелегко: профессор не умел программировать, потому что с детства считал, что программировать – очень просто, следовательно, учиться этому бессмысленно. А сможете ли вы решить эту задачу?

Вам дано q запросов. Каждый запрос состоит из одного числа n. На каждом шаге вы можете произвести одну из двух операций:

1. вычесть из n единицу;
2. если n = a × b и 1  <  a  ≤  b, то заменить n на b.

Определите минимальное количество операций, которые превратят n в ноль.