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.
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.
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.
2 4 5 2 6 4 3
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