## XIV POI Stage I - Queries

View as PDF

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 , , and , find the number of integer pairs satisfying the following conditions:

• ,
• ,
• , where is the greatest common divisor of and .

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 , denoting the number of queries. The following lines contain three integers each: , , and , separated by single spaces. Each triplet denotes a single query.

#### Output

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

#### Sample Input

2
4 5 2
6 4 3

#### Sample Output

3
2

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