SP12241 HS12PRIM - Classification from Erdős and Selfridge

Erdős Pál 和 John Selfridge 提出了一种对素数的分类方法：对任意素数 $p$，如果 $p-1$ 的最大素因子是 $2$ 或 $3$，那么 $p$ 归为第一类。否则，$p$ 的类别为 $c+1$，其中 $c$ 是 $p-1$ 的所有素因子中最大的一类。特别地，我们将 $p=2$ 定义为第一类。 举个例子，素数 $p=89$ 属于第三类，因为 $p-1=2^3 \cdot 11$，其中 $2$ 属于第一类，而 $11$ 属于第二类（因为 $11-1=2 \cdot 5$，且 $2$ 和 $5$ 都在第一类）。你的任务是计算给定闭区间内各类素数（最多到第十三类）的数量。

第一行包含整数 $T$，代表测试用例的数量，满足 $T \leq 4$。接下来的 $T$ 行中，每行含有两个整数 $a$ 和 $b$，表示感兴趣的闭区间的起始和终止位置，且满足 $0 < a \leq b \leq 10^6$。

对于每个测试用例，按照编号输出，并以正确的格式显示该区间内每一类（最多到第十三类）的素数分布。具体格式可参考样例输入和输出。

- $T \leq 4$ - $0 < a \leq b \leq 10^6$ **本翻译由 AI 自动生成**