SPOJ.com - Problem ETFD

ETFD - Euler Totient Function Depth

#number-theory

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₀ = 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.

Input

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

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

Constraints

T < 10001
1 ≤ m ≤ n ≤ 10⁶
0 ≤ k < 20

Example

Input:
5
1 3 1
1 10 2
1 10 3
1 100 3
1 1000000 17

Output:
1
3
5
8
287876

Explanation: suppose number is 5 ; its depth will be 3. ( 5 → 4 → 2 → 1 )

Note: Depth for 1 is 0.

Submit solution!

hide comments

< Previous 1 2 3 4 Next >

	RIVU DAS: 2015-01-27 16:42:48 @Lakshman - Hey, can you check why i am getting WA?? --(Lakshman)--> You have some WA. for example 70 857815 4 answer is 0 @Lakshman - Thanks..i was just doing a stupid mistake. Bdw, nice question. --(Lakshman)--> Thanks for apperciation @Rivu Last edit: 2015-01-28 06:31:52
	Mitch Schwartz: 2015-01-15 15:05:59 Changing k <= 20 to k < 20 makes no sense. I checked that k = 20 doesn't appear in the input. But it should. --Francky--> I didn't change that, only clean text. I agree that it should, and even k<=1024, but it's maybe too late for that. --wisfaq--> apart from which k's appear in the input, it's not necessary to mention constraints on k in the text at all. psolvers can verify which values of k occur in the range from 1 to 1000000 and catch invalid ones in the input, can't they? Even if Lakshman is busy it shouldn't be too much trouble to change that and hide the comments that reference the values of k. Last edit: 2015-01-15 21:14:13
	Francky: 2015-01-15 13:57:43 Here are some proposed improvements for description, as I find it a bit unclear. A) 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. B)"as described above" is useless. C) Output for each test case one line containing the count of numbers whose depth equals to k in given range [m,n]. (note too the typo in "equlas") D) for the constraints, it would have been fun to set 0 <= k < 1024, even if we know that ... ;-) --Lakshman->Thanks @Francky description updated, and regarding constraints I will work more on this and I will let you know once I am ready with that. These days I am a bit busy. --Francky--> I took the liberty to clean the html tags, and for the constraints it's too late. Last edit: 2015-01-15 14:38:51
	[Lakshman]: 2015-01-15 13:57:43 @All I will update the description and IO file soon. Apologize for inconvenience. EDIT1:: Problem description IO files & Time Limit updated. EDIT2:: Rejudge DONE! Now you can submit your solution. Last edit: 2015-01-15 14:31:23
	Francky: 2015-01-15 13:57:43 This problem is (for now) a riddle : how to guess what could be the exact definition of depth ? Here we have depth(1)=depth(2)=0. It's not very good. Problem hidden waiting for fix, and rejudge. I wish a better time limit for Python users by the way. edit : the problem is likely to stay in classical when the description and data are updated. Last edit: 2015-01-15 00:18:31
	abdou_93: 2015-01-15 13:57:43 how depth(1) = depth(2) = 0 and you saying that depth(5) = 2 !!! @Francky.thanks for staying it in classical section Last edit: 2015-01-15 00:42:15
	Francky: 2015-01-15 13:57:43 +1 with Mitch for A) depth(5) should be 3!!! and depth(1) = 0, and 1 is the only number with a null depth. And B) >and found an interesting property of ETF. It should be stated that it is that recursive call to ETF leads to 1. Nothing more is need. C) Description is quite unclear ; exact definition of depth isn't given. Please update, and clean IO files if need, and rejudge. D) Please make sure your code can get AC with some slow languages. You can let us your timings it is often appreciate.
	Mitch Schwartz: 2015-01-15 13:57:43 There is a strange "alignment" issue. Depth is defined in terms of distance to 1, but example shows distance to 2. That would leave depth(1) undefined, and depth(n)=20 impossible in the given range. It seems natural to take instead depth(5)=3, which would make 0 <= k <= 20 coincide with the range of possible depths. Also, typo report: "Exapmle". Last edit: 2015-01-14 22:23:38

Submit solution!

Added by:	[Lakshman]
Date:	2015-01-14
Time limit:	2s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64 JS-MONKEY
Resource:	ETF