Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

C. Turtle Fingers: Count the Values of k
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given three positive integers a, b and l (a,b,l>0).

It can be shown that there always exists a way to choose non-negative (i.e. 0) integers k, x, and y such that l=kaxby.

Your task is to find the number of distinct possible values of k across all such ways.

Input

The first line contains the integer t (1t104) — the number of test cases.

The following t lines contain three integers, a, b and l (2a,b100, 1l106) — description of a test case.

Output

Output t lines, with the i-th (1it) line containing an integer, the answer to the i-th test case.

Example
Input
11
2 5 20
2 5 21
4 6 48
2 3 72
3 5 75
2 2 1024
3 7 83349
100 100 1000000
7 3 2
2 6 6
17 3 632043
Output
6
1
5
12
6
11
24
4
1
3
24
Note

In the first test case, a=2,b=5,l=20. The possible values of k (and corresponding x,y) are as follows:

  • Choose k=1,x=2,y=1. Then kaxby=12251=20=l.
  • Choose k=2,x=1,y=1. Then kaxby=22151=20=l.
  • Choose k=4,x=0,y=1. Then kaxby=42051=20=l.
  • Choose k=5,x=2,y=0. Then kaxby=52250=20=l.
  • Choose k=10,x=1,y=0. Then kaxby=102150=20=l.
  • Choose k=20,x=0,y=0. Then kaxby=202050=20=l.

In the second test case, a=2,b=5,l=21. Note that l=21 is not divisible by either a=2 or b=5. Therefore, we can only set x=0,y=0, which corresponds to k=21.

In the third test case, a=4,b=6,l=48. The possible values of k (and corresponding x,y) are as follows:

  • Choose k=2,x=1,y=1. Then kaxby=24161=48=l.
  • Choose k=3,x=2,y=0. Then kaxby=34260=48=l.
  • Choose k=8,x=0,y=1. Then kaxby=84061=48=l.
  • Choose k=12,x=1,y=0. Then kaxby=124160=48=l.
  • Choose k=48,x=0,y=0. Then kaxby=484060=48=l.