## 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.

### 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^6 0 ≤ k < 20

### Example

Input:5 1 3 1 1 10 2 1 10 3 1 100 3 1 1000000 17Output: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.

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 |