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
```

#### 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