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 \le x \le a~,
• ~1 \le y \le 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.

Write a program which:

• reads from the standard input a list of queries, which the Byteasar has to give the 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 \le n \le 50\,000)~, denoting the number of queries. The following ~n~ lines contain three integers each: ~a~, ~b~, and ~d~ ~(1 \le d \le a,b \le 50\,000)~, separated by single spaces. Each triplet denotes a single query.

Output

Your program 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.

Sample Input

2
4 5 2
6 4 3

Sample Output

3
2

Judge Input Metadata

Note - because DMOJ judges are substantially faster than POI judges, the time limits on DMOJ are 2/3rds the official time limits. However, the minimum time limit is always 0.1 seconds.

$ wc -l zap*.in
     11 zap1.in - official TL 0.1s
     38 zap2.in - official TL 0.1s
    101 zap3.in - official TL 0.1s
  12501 zap4.in - official TL 0.3s
  50000 zap5.in - official TL 3.0s
  50001 zap6.in - official TL 3.5s
    101 zap7.in - official TL 0.4s
   3125 zap8.in - official TL 0.4s
  12502 zap9.in - official TL 1.5s
  50001 zap10.in - official TL 10.5s
  49730 zap11.in - official TL 8.0s
  50001 zap12.in - official TL 0.2s
  49771 zap13.in - official TL 4.5s
  50001 zap14.in - official TL 4.0s
  50001 zap15.in - official TL 10.0s
      3 zap0.in - official TL 0.1s
      2 zap1ocen.in - official TL 0.1s
      4 zap2ocen.in - official TL 0.1s
      6 zap3ocen.in - official TL 0.1s
  50001 zap4ocen.in - official TL 0.2s