CF932B Recursive Queries

Let us define two functions $ f $ and $ g $ on positive integer numbers.  You need to process $ Q $ queries. In each query, you will be given three integers $ l $ , $ r $ and $ k $ . You need to print the number of integers $ x $ between $ l $ and $ r $ inclusive, such that $ g(x)=k $ .

The first line of the input contains an integer $ Q $ ( $ 1

For each query, print a single line containing the answer for that query.

In the first example: - $ g(33)=9 $ as $ g(33)=g(3×3)=g(9)=9 $ - $ g(47)=g(48)=g(60)=g(61)=6 $ - There are no such integers between $ 47 $ and $ 55 $ . - $ g(4)=g(14)=g(22)=g(27)=g(39)=g(40)=g(41)=g(58)=4 $