题目描述

小游觉得前一道素数题太简单了，根本没难倒小胡，于是他再次考考小胡

小游给小胡三个整数 \(a\)，\(b\)，\(n\)（取值范围均为 \([2, 10^6]\)），求满足以下条件的素数 \(k\) 的个数：


\[ a^k \leq b^n \]


其中 \(k\) 必须是素数（质数），并且 \(k \geq 2\)。


这次小胡被小游给难住了，聪明的你快帮帮小胡吧

输入格式

第一行输入T，表示有T个测试样例（1

第2~T+1行，每行三个整数  \(a\)，\(b\)，\(n\) 以空格分隔（取值范围均为 \([2, 10^6]\)）。

输出格式

一个整数，表示满足条件的素数 (k) 的个数。

1
2 2 2

1