XIV POI Stage I - Queries

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 7.0s
Memory limit: 32M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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

$ 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

Comments

There are no comments at the moment.