Byteasar the Cryptographer works on breaking the code of BSA (Byteotian Security Agency). He has already found out that whilst deciphering a message he will have to answer multiple queries of the form “for given integers $a$, $b$ and $d$, find the number of integer pairs $(x, y)$ satisfying the following conditions:

• $1 ≤ x ≤ a$,
• $1 ≤ y ≤ b$,
• $\gcd(x,y) = d$, where $\gcd(x,y)$ is the greatest common divisor of $x$ and $y$.”

Byteasar would like to automate his work, so he has asked for your help.

Task

Write a programme which:

• reads from the standard input a list of queries, which the Byteasar has to give answer to,
• calculates answers to the queries,
• writes the outcome to the standard output.

Input

The first line of the standard input contains one integer $n$ ($1 ≤ n ≤ 50\,000$), denoting the number of queries. The following $n$ lines contain three integers each: $a$, $b$ and $d$ ($1 ≤ d ≤ a,b ≤ 50\,000$), separated by single spaces. Each triplet denotes a single query.

Output

Your programme should write $n$ lines to the standard output. The $i$'th line should contain a single integer: the answer to the $i$'th query from the standard input.

Example

Input

2
4 5 2
6 4 3

Output

3
2

The pairs satisfying the first query are: (2,2), (2,4) and (4,2). The pairs satisfying the second query are: (6,3) and (3,3).