CLUSCL_tester.java

import java.io.InputStream;

class Fraction
{
    long num, den;
    Fraction(long n, long d)
    {
        num = n;    den = d;
    }
    Fraction(double n, int places)
    {
        num = (long)n;    den = 1;    n -= (long)n;
        for(;places > 0; --places)
        {
            n *= 10;    num = (10 * num) + (long)n; n -= (long)n;
            den *= 10;
        }
    }
    long gcd(long a, long b)
    {
        long temp;
        a = Math.abs(a);    b = Math.abs(b);
        while(b > 0)
        {
            temp = b;  b = a % b;   a = temp;
        }
        return a;
    }
    void reduce()
    {
        long gcd = gcd(num, den);
        num /= gcd;     den /= gcd;
    }
    void add(Fraction f, long MOD)
    {
        num = ((num * f.den) % MOD + (f.num * den) % MOD) % MOD;
        den *= f.den;   den %= MOD;
    }
    void multiply(Fraction f,long MOD)
    {
        num *= f.num;   num %= MOD;
        den *= f.den;   den %= MOD;
    }
    void invert()
    {
        long temp = num;    num = den;  den = temp;
    }
    void negate()
    {
        if(den < 0) den = -den;
        else num = -num;
    }
    double decimalValue()
    {
        return num / (double) den;
    }
    long modular_pow(long base, long exponent, long MOD)
    {
        long result = 1;
        while (exponent > 0)
        {
            if (exponent % 2 == 1)
                result = (result * base) % MOD;
            exponent = exponent >> 1;
            base = (base * base) % MOD;
        }
        return result;
    }
    void power(long exp, long MOD)
    {
        num = modular_pow(num, exp, MOD);
        den = modular_pow(den, exp, MOD);
    }
    long modInverse(long num, long MOD)
    {
        return modular_pow(num, MOD - 2, MOD);
    }
    void print()
    {
        System.out.println(num + " / " + den);
    }
}
class StartHere
{
    static IO1 io = new IO1(System.in);
    static final Fraction ONE = new Fraction(1l, 1l);
    static final Fraction ONEi = new Fraction(-1l, 1l);
    static final Fraction TWO = new Fraction(2l, 1l);
    
    public static void main(String[] args) throws Exception
    {
        for(int tc = io.nextInt(); tc > 0; --tc)
        {
            Fraction fr = new Fraction(io.nextLong(), io.nextLong());
            fr.reduce();
            fr.add(ONEi, Long.MAX_VALUE);
            if((fr.num < 0 && fr.den >= 0) || (fr.num >= 0 && fr.den < 0))
                fr.negate();
            fr.multiply(TWO, Long.MAX_VALUE);
            fr.invert();
            fr.reduce();
            fr.multiply(new Fraction(io.nextLong()-1, 1l), Long.MAX_VALUE);
            fr.reduce();
            
            long val = 1 + (long) fr.decimalValue();
            io.println(val);
        }
        io.flush();
    }
}
 
class IO1
{
    static byte[] buf = new byte[2048];
    static int index, total;
    static InputStream in;
    static StringBuilder sb = new StringBuilder();
    
 
    IO1(InputStream is)
    {
        in = is;
    }
 
    int scan() throws Exception
    {
        if(index>=total){
            index = 0;
            total = in.read(buf);
            if(total<=0)
                return -1;
        }
        return buf[index++];
    }
 
    String next() throws Exception
    {
        int c;
        for(c=scan(); c<=32; c=scan());
        StringBuilder sb = new StringBuilder();
        for(; c>32; c=scan())
            sb.append((char)c);
        return sb.toString();
    }
 
    int nextInt() throws Exception
    {
        int c, val = 0;
        for(c=scan(); c<=32; c=scan());
        boolean neg = c=='-';
        if(c=='-' || c=='+')
            c = scan();
        for(; c>='0' && c<='9'; c=scan())
            val = (val<<3) + (val<<1) + (c&15);
        return neg?-val:val;
    }
    long nextLong() throws Exception
    {
        int c;long val = 0;
        for(c=scan(); c<=32; c=scan());
        boolean neg = c=='-';
        if(c=='-' || c=='+')
            c = scan();
        for(; c>='0' && c<='9'; c=scan())
            val = (val<<3) + (val<<1) + (c&15);
        return neg?-val:val;
    }
    void print(Object a)
    {
        sb.append(a.toString());
    }
    void println(Object a)
    {
        sb.append(a.toString()).append("\n");
    }
    void println()
    {
        sb.append("\n");
    }
    void flush()
    {
        System.out.print(sb);
        sb = new StringBuilder();
    }
}