#T2629. 统计右侧不同素数的个数

统计右侧不同素数的个数

题目描述

给定 nn 个整数。对每个位置,统计它右侧有多少种不同的素数。同一个素数在右侧出现多次时,只计一次。素数是大于 1 且只有 1 和自身两个正因数的整数。

输入格式

第一行输入正整数 nn。第二行输入 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n,用空格隔开。

输出格式

输出一行 nn 个整数,依次对应原序列的第 1 到第 nn 个位置。相邻结果用一个半角空格隔开。最后一个位置的右侧为空,结果为 0。

数据范围

1≤n≤1041 \le n \le 10^4,−105≤ai≤105-10^5 \le a_i \le 10^5。

输入输出样例

样例输入 1

7
2 4 3 2 3 9 5

样例输出 1

3 3 3 2 1 1 0

样例输入 2

4
2 2 2 2

样例输出 2

1 1 1 0

样例解释

样例 1 中,第一个数右侧的素数有 3、2、3、5。其中 3 只计一次,所以第一个结果为 3。