题目描述

Milk 有一个数列 $a$。

Milk 的任务是把数列变成单调不降的。每次操作她可以选择数列中一个大于 $1$ 的数 $a_i$，再选择它的一个质因子，然后把 $a_i$ 修改为 $\frac{a_i}p$。她可以做任意多次操作，也可以完全不做操作。

Milk 非常追求效率。她想知道，最少需要多少次操作可以使得 $a$ 单调不降。

输入格式

第一行一个整数 $T$。

接下来 $T$ 组，第一行一个整数 $n$，表示数列长度。

接下来一行 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

输出格式

共 $T$ 行，每行一个整数，表示最少需要的操作次数。

3
3
3 2 1
6
1 1 4 5 1 4
3
998 244 353

2
3
1

数据范围

• 对于 $30\%$ 的数据，$1 \le T \le 10$，$1 \le n \le 10^3$，$1 \le a_i \le 10^3$；
• 对于 $60\%$ 的数据，$1 \le a_i \le 10^3$；
• 对于 $100\%$ 的数据，$1 \le T \le 2 \cdot 10^5$，$1 \le n, \sum n \le 2 \cdot 10^5$，$1 \le a_i \le 5 \cdot 10^5$。