刻苦学习的高中3年生·唯我成幸，为了获得免除大学学费的“特别VIP推荐”资格，而要去担任为备考而苦战的同级生们的教育指导员。教导的对象是“文学之森的睡美人”古桥文乃和“机关精巧的拇指姑娘”绪方理珠这两位学园顶尖的天才美少女！原本以为她们的学习能力完美无缺，没想到对于不擅长的学科却完全无能……！？成幸一边被充满个性的“学不来女孩”们玩弄于股掌之间，一边为了让她们努力通过大学考试！无论学习还是恋爱都“学不来”的天才们的恋爱喜剧，就此开幕！！

有一天，古桥文乃拿着如下问题请教唯我成幸：“有 $n$ 个数字‘$1$’，现将用这些数字‘$1$’通过加法、乘法和括号运算符求得正整数 $s$ ，求 $n$ 的最小值。”
唯我成幸应该怎么帮助她呢？

第一行输入 $T$ ，表示接下来有 $T$ 组测试样例。$1 \leq T \leq 2×10^{5}$
接下来，对于每一组测试样例，在一行内输入一个数字 $s$ 。$1 \leq s \leq 10^{4}$

对于每一组测试样例，输出最小值 $n_{min}$ 并换行。

2
3
4

3
4

样例解释：
第一组样例： $3=1+1+1$ ，最少 $3$ 个。
第二组样例： $4=1+1+1+1$ 或 $(1+1)×(1+1)$ ，最少 $4$ 个。
（注：此题数据已于赛后得到加强；原本为“加减乘除括号”，后改为“加乘括号”）

Enal WIT第二届程序设计竞赛(现场赛)