polski
Task Queries (zap)
Queries
Memory limit: 32 MB
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 
".
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 
(
),
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 programme 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.
Example
For the input data:
2 4 5 2 6 4 3
the correct result is:
3 2
The pairs satisfying the first query are: 
, 
and 
. The pairs satisfying the second query are:
and 
.
Task author: Jakub Radoszewski.