package no061b; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.math.BigInteger; import java.util.InputMismatchException; import java.util.NoSuchElementException; public class Main { static IO io = new IO(); public static void main(String[] args) { int q = io.nextInt(); TC: for(int qq=0;qq 0) { long temp; long t = a / b; a -= t * b; temp = a; a = b; b = temp; u -= t * v; temp = u; u = v; v = temp; } return (u % mod + mod) % mod; } // x mod m public static long[] linearCongruence(long[] A,long[] B,long[] M) { long x = 0; long m = 1; for(int i=0;i Integer.MAX_VALUE) { throw new NumberFormatException(); } return (int) nl; } public char nextChar() { if (!hasNext()) { throw new NoSuchElementException(); } return (char) readByte(); } public double nextDouble() { return Double.parseDouble(next());} public int[] nextIntArray(int n) { int[] a = new int[n]; for(int i=0;i