SP22382 ETFD - Euler Totient Function Depth

Lucky is fond of Number theory, one day he was solving a problem related to Euler Totient Function (phi) and found an interesting property of phi : phi(1) = 1, and for x > 1: phi(x) < x. So if we define a sequence with a $ _{0} $ = x, and for n > 0: a $ _{n} $ = phi(a $ _{n-1} $ ), this sequence will be constant equal to 1 starting from some point. Lets define depth(x) as minimal n such that a $ _{n} $ = 1. Now he is wondering how many numbers in a given range have depth equal to given number **k**. As you are a good programmer help Lucky with his task.

Your input will consist of a single integer **T** followed by a newline and **T** test cases. Each test cases consists of a single line containing integers **m**, **n**, and **k**.

Output for each test case one line containing the count of all numbers whose depth equals to **k** in given range \[**m**, **n**\].