An infinite integer sequence (S) can be generated from the following quadratic equation S(x) = ax2 + bx + c [a, b, c are non-negative integers] and x = 0 → ∞ (x is integer) S(x) is the x-th element of sequence S. For example, if a = 0, b = 1 and c = 0, then S(x) = x Sothesequencewillbe: 0,1,2,3,4,5,6,7,8,9,10,...∞ A fraction p/q (p and q are relatively prime) is associated with the sequence S in such way that () ∑∞ x+1 p= S(x) 1 qx=0 10 Here sequence 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...∞ is associated with fraction 1 = 0 + 1 + 2 + 3 +...=0.0123456790... 81 10 102 103 104 (explained in right) In summary, for a given triplet a, b, c there will be a sequence S and for a sequence S there will be a fraction p/q But for this problem fraction p/q will be given. You have to find out how many integer triples (a, b, c) exist for some given limit L where 0 ≤ a, b, c ≤ L. Input Given T (≤ 104) denoting number of test cases. Each case consists of 3 positive integers p, q and L. p and q are relatively prime to each other. Listhemaximumvaluefora,b,c. Denominatorq>1andp,q≤107 andL≤105 Output You have to report the number of integer triples (a, b, c) that can be formed where 0 ≤ a, b, c ≤ L. See sample Input output for format. Sample Input 3 1 81 100 2 3 20 2 3 100000 Sample Output Case 1: 1 Case 2: 7 Case 3: 21