import java.awt.Point;
import java.io.*;
import java.math.BigInteger;
import java.nio.charset.*;
import java.util.*;
import java.util.function.*;
class Main {
	static boolean autoFlush = false;
	static SimpleScanner sc = new SimpleScanner( System.in );
	static SimpleWriter out = new SimpleWriter( System.out, autoFlush );
	public static void main ( String[] args ) {

		int N = sc.nextInt();
		while(N-->0){
			long x = sc.nextLong();
			out.print(x);
			out.print(" ");
			out.println(MathFunction.isPrime(x)?1:0);
		}

		out.close();
	}
}
/*////////////////////////////////////////////////////////////////////////////////////////////
                                        * My Library *

                                        @author  viral
*/////////////////////////////////////////////////////////////////////////////////////////////
class Factorial {
	long[] fact, inFact;
	long mod;
	Factorial ( int N, long mod ) {
		fact = new long[N + 1];
		fact[0] = fact[1] = 1;
		for ( int i = 2; i <= N; ++i ) {
			fact[i] = fact[i - 1] * i % mod;
		}
		inFact = new long[N + 1];
		inFact[N] = MathFunction.modPow( fact[N], mod - 2, mod );
		for ( int i = N; i > 0; --i ) {
			inFact[i - 1] = inFact[i] * i % mod;
		}
		inFact[0] = 1;

		this.mod = mod;
	}
	long getFact ( int num ) {
		return fact[num];
	}
	long getInFact ( int num ) {
		return inFact[num];
	}
	long getInverse ( int num ) {
		return fact[num - 1] * inFact[num] % mod;
	}
	long getCombi ( int a, int b ) {
		if ( a < b || a < 0 || b < 0 ) {
			return 0;
		}
		return ( fact[a] * inFact[a - b] % mod ) * inFact[b] % mod;
	}
}

class ArrayFunction {
	static int[][] rotateR ( int[][] array ) {
		int[][] ans = new int[array[0].length][array.length];
		for ( int i = 0; i < ans.length; ++i ) {
			for ( int j = 0; j < ans[i].length; ++j ) {
				ans[i][j] = array[ans[i].length - j - 1][i];
			}
		}
		return ans;
	}
	static long[][] rotateR ( long[][] array ) {
		long[][] ans = new long[array[0].length][array.length];
		for ( int i = 0; i < ans.length; ++i ) {
			for ( int j = 0; j < ans[i].length; ++j ) {
				ans[i][j] = array[ans[i].length - j - 1][i];
			}
		}
		return ans;
	}
	static char[][] rotateR ( char[][] array ) {
		char[][] ans = new char[array[0].length][array.length];
		for ( int i = 0; i < ans.length; ++i ) {
			for ( int j = 0; j < ans[i].length; ++j ) {
				ans[i][j] = array[ans[i].length - j - 1][i];
			}
		}
		return ans;
	}
	static double[][] rotateR ( double[][] array ) {
		double[][] ans = new double[array[0].length][array.length];
		for ( int i = 0; i < ans.length; ++i ) {
			for ( int j = 0; j < ans[i].length; ++j ) {
				ans[i][j] = array[ans[i].length - j - 1][i];
			}
		}
		return ans;
	}
	static boolean[][] rotateR ( boolean[][] array ) {
		boolean[][] ans = new boolean[array[0].length][array.length];
		for ( int i = 0; i < ans.length; ++i ) {
			for ( int j = 0; j < ans[i].length; ++j ) {
				ans[i][j] = array[ans[i].length - j - 1][i];
			}
		}
		return ans;
	}
	static <E> E[][] rotateR ( E[][] array, E[][] ans ) {
		for ( int i = 0; i < ans.length; ++i ) {
			for ( int j = 0; j < ans[i].length; ++j ) {
				ans[i][j] = array[ans[i].length - j - 1][i];
			}
		}
		return ans;
	}
	static int[][] rotateL ( int[][] array ) {
		int[][] ans = new int[array[0].length][array.length];
		for ( int i = 0; i < ans.length; ++i ) {
			int index = i;
			Arrays.setAll( ans[i], k -> array[k][ans.length - index - 1] );
		}
		return ans;
	}
	static long[][] rotateL ( long[][] array ) {
		long[][] ans = new long[array[0].length][array.length];
		for ( int i = 0; i < ans.length; ++i ) {
			int index = i;
			Arrays.setAll( ans[i], k -> array[k][ans.length - index - 1] );
		}
		return ans;
	}
	static char[][] rotateL ( char[][] array ) {
		char[][] ans = new char[array[0].length][array.length];
		for ( int i = 0; i < ans.length; ++i ) {
			for ( int j = 0; j < ans[i].length; ++j ) {
				ans[i][j] = array[j][ans.length - i - 1];
			}
		}
		return ans;
	}
	static double[][] rotateL ( double[][] array ) {
		double[][] ans = new double[array[0].length][array.length];
		for ( int i = 0; i < ans.length; ++i ) {
			for ( int j = 0; j < ans[i].length; ++j ) {
				ans[i][j] = array[j][ans.length - i - 1];
			}
		}
		return ans;
	}
	static boolean[][] rotateL ( boolean[][] array ) {
		boolean[][] ans = new boolean[array[0].length][array.length];
		for ( int i = 0; i < ans.length; ++i ) {
			for ( int j = 0; j < ans[i].length; ++j ) {
				ans[i][j] = array[j][ans.length - i - 1];
			}
		}
		return ans;
	}
	static <E> E[][] rotateL ( E[][] array, E[][] ans ) {
		for ( int i = 0; i < ans.length; ++i ) {
			for ( int j = 0; j < ans[i].length; ++j ) {
				ans[i][j] = array[j][ans.length - i - 1];
			}
		}
		return ans;
	}
	static int lis ( int[] array ) {
		return lis( array, false );
	}
	static int lis ( int[][] arrays, int p ) {
		return lis( arrays, p, false );
	}
	static int lis ( long[] array ) {
		return lis( array, false );
	}
	static int lis ( long[][] arrays, int p ) {
		return lis( arrays, p, false );
	}
	static int lis ( int[] array, boolean include ) {
		int[] list = new int[array.length];
		Arrays.fill( list, Integer.MAX_VALUE );
		for ( int num: array ) {
			int index = include ? Searcher.overSearch( list, num ) : Searcher.upSearch( list, num );
			list[index] = Math.min( list[index], num );
		}
		int answer = Searcher.underSearch( list, Integer.MAX_VALUE );
		return answer + 1;
	}
	static int lis ( int[][] arrays, int p, boolean include ) {
		int[] list = new int[arrays.length];
		Arrays.fill( list, Integer.MAX_VALUE );
		for ( int[] array: arrays ) {
			int index = include ? Searcher.overSearch( list, array[p] ) : Searcher.upSearch( list, array[p] );
			list[index] = Math.min( list[index], array[p] );
		}
		int answer = Searcher.underSearch( list, Integer.MAX_VALUE );
		return answer + 1;
	}
	static int lis ( long[] array, boolean include ) {
		long[] list = new long[array.length];
		Arrays.fill( list, Long.MAX_VALUE );
		for ( long num: array ) {
			int index = include ? Searcher.overSearch( list, num ) : Searcher.upSearch( list, num );
			list[index] = Math.min( list[index], num );
		}
		int answer = Searcher.underSearch( list, Long.MAX_VALUE );
		return answer + 1;
	}
	static int lis ( long[][] arrays, int p, boolean include ) {
		long[] list = new long[arrays.length];
		Arrays.fill( list, Long.MAX_VALUE );
		for ( long[] array: arrays ) {
			int index = include ? Searcher.overSearch( list, array[p] ) : Searcher.upSearch( list, array[p] );
			list[index] = Math.min( list[index], array[p] );
		}
		int answer = Searcher.underSearch( list, Long.MAX_VALUE );
		return answer + 1;
	}
	static int[][] topologicalSort ( ArrayList<ArrayList<Integer>> route ) {
		int[] count = new int[route.size()];
		int pathCount = 0;
		for ( ArrayList<Integer> path: route ) {
			for ( int point: path ) {
				++pathCount;
				++count[point];
			}
		}
		ArrayDeque<Integer> deq = new ArrayDeque<>();
		for ( int i = 1; i < count.length; ++i ) {
			if ( count[i] == 0 ) {
				deq.add( i );
			}
		}
		int[][] ans = new int[pathCount][2];
		int index = 0;
		while ( deq.size() > 0 ) {
			int nowP = deq.pollFirst();
			for ( int nextP: route.get( nowP ) ) {
				ans[index][0] = nowP;
				ans[index++][1] = nextP;
				if ( --count[nextP] == 0 ) {
					deq.add( nextP );
				}
			}
		}
		return ans;
	}
	static int[][] topologicalSort ( int[][] route ) {
		int[] count = new int[route.length];
		int pathCount = 0;
		for ( int[] path: route ) {
			for ( int point: path ) {
				++pathCount;
				++count[point];
			}
		}
		ArrayDeque<Integer> deq = new ArrayDeque<>();
		for ( int i = 1; i < count.length; ++i ) {
			if ( count[i] == 0 ) {
				deq.add( i );
			}
		}
		int[][] ans = new int[pathCount][2];
		int index = 0;
		while ( deq.size() > 0 ) {
			int nowP = deq.pollFirst();
			for ( int nextP: route[nowP] ) {
				ans[index][0] = nowP;
				ans[index++][1] = nextP;
				if ( --count[nextP] == 0 ) {
					deq.add( nextP );
				}
			}
		}
		return ans;
	}
	static boolean nextPermutation ( int[] array ) {
		int index1 = 0;
		for ( int i = 1; i < array.length; ++i ) {
			if ( array[i - 1] < array[i] ) {
				index1 = i;
			}
		}
		if ( --index1 < 0 ) {
			return false;
		}
		int index2 = 0;
		int min = Integer.MAX_VALUE;
		for ( int i = index1 + 1; i < array.length; ++i ) {
			if ( MathFunction.rangeCheckOpen( array[i], array[index1], min ) ) {
				min = array[i];
				index2 = i;
			}
		}
		int temp = array[index1];
		array[index1] = array[index2];
		array[index2] = temp;
		Arrays.sort( array, index1 + 1, array.length );
		return true;
	}
	static boolean nextPermutation ( long[] array ) {
		int index1 = 0;
		for ( int i = 1; i < array.length; ++i ) {
			if ( array[i - 1] < array[i] ) {
				index1 = i;
			}
		}
		if ( --index1 < 0 ) {
			return false;
		}
		int index2 = 0;
		long min = Long.MAX_VALUE;
		for ( int i = index1 + 1; i < array.length; ++i ) {
			if ( MathFunction.rangeCheckOpen( array[i], array[index1], min ) ) {
				min = array[i];
				index2 = i;
			}
		}
		long temp = array[index1];
		array[index1] = array[index2];
		array[index2] = temp;
		Arrays.sort( array, index1 + 1, array.length );
		return true;
	}
	static boolean nextPermutation ( char[] array ) {
		int index1 = 0;
		for ( int i = 1; i < array.length; ++i ) {
			if ( array[i - 1] < array[i] ) {
				index1 = i;
			}
		}
		if ( --index1 < 0 ) {
			return false;
		}
		int index2 = 0;
		int min = Integer.MAX_VALUE;
		for ( int i = index1 + 1; i < array.length; ++i ) {
			if ( MathFunction.rangeCheckOpen( array[i], array[index1], min ) ) {
				min = array[i];
				index2 = i;
			}
		}
		char temp = array[index1];
		array[index1] = array[index2];
		array[index2] = temp;
		Arrays.sort( array, index1 + 1, array.length );
		return true;
	}
	static <E extends Comparable<E>> boolean nextPermutation ( E[] array ) {
		int index1 = 0;
		for ( int i = 1; i < array.length; ++i ) {
			if ( array[i - 1].compareTo( array[i] ) < 0 ) {
				index1 = i;
			}
		}
		if ( --index1 < 0 ) {
			return false;
		}
		int index2 = -1;
		E min = null;
		int subIndex = -1;
		E max = array[index1];
		for ( int i = index1 + 1; i < array.length; ++i ) {
			if ( min == null || MathFunction.rangeCheckOpen( array[i], array[index1], min ) ) {
				min = array[i];
				index2 = i;
			}
			if ( max.compareTo( array[i] ) < 0 ) {
				subIndex = i;
				max = array[i];
			}
		}
		E temp;
		if ( index2 == -1 ) {
			temp = array[subIndex];
			array[subIndex] = array[index1];
		}
		else {
			temp = array[index2];
			array[index2] = array[index1];
		}
		array[index1] = temp;
		Arrays.sort( array, index1 + 1, array.length );
		return true;
	}
}
class Converter {
	static String reverse ( String str ) {
		StringBuilder sb = new StringBuilder();
		for ( int i = str.length() - 1; i >= 0; --i ) {
			sb.append( str.charAt( i ) );
		}
		return sb.toString();
	}
}
class MathFunction {
	static int[] numberForIntPrime = {2, 7, 61};
	static long[] numberForLongPrime = {2, 7, 61, 325, 9375, 28178, 450775, 9780504, 1795265022};
	static long gcd ( long a, long b ) {
		a = Math.abs( a );
		b = Math.abs( b );
		if ( b == 0 ) {
			return a;
		}
		long temp;
		while ( ( temp = a % b ) != 0 ) {
			a = b;
			b = temp;
		}
		return b;
	}
	static long lcm ( long a, long b ) {
		return a / gcd( a, b ) * b;
	}
	static boolean isPrime ( long n ) {
		n = Math.abs( n );
		if ( n == 2L ) {
			return true;
		}
		if ( n == 1L || ( n & 1L ) == 0L ) {
			return false;
		}
		if ( n <= 4_759_123_141L ) {
			return isPrimeForInt( n );
		}
		if ( n <= Long.MAX_VALUE / n ) {
			return isPrimeForLong( n );
		}
		return isPrimeForBigInteger( n );
	}
	static boolean isPrimeForInt ( long n ) {
		long d = n - 1;
		while ( ( d & 1 ) == 0L ) {
			d >>= 1;
		}
		for ( long a: numberForIntPrime ) {
			if ( a >= n ) {
				return true;
			}
			long t = d;
			long y = MathFunction.modPow( a, t, n );
			while ( t < n - 1L && y != 1 && y != n - 1 ) {
				y = y * y % n;
				t <<= 1;
			}
			if ( y != n - 1 && ( t & 1L ) == 0 ) {
				return false;
			}
		}
		return true;
	}
	static boolean isPrimeForLong ( long n ) {
		long d = n - 1L;
		while ( ( d & 1 ) == 0L ) {
			d >>= 1;
		}
		for ( long a: numberForLongPrime ) {
			if ( a >= n ) {
				return true;
			}
			long t = d;
			long y = MathFunction.modPow( a, t, n );
			while ( t < n - 1L && y != 1 && y != n - 1 ) {
				y = y * y % n;
				t <<= 1;
			}
			if ( y != n - 1 && ( t & 1L ) == 0 ) {
				return false;
			}
		}
		return true;
	}
	static boolean isPrimeForBigInteger ( long n ) {
		long d = n - 1L;
		while ( ( d & 1 ) == 0L ) {
			d >>= 1;
		}
		BigInteger bigN = BigInteger.valueOf( n );
		BigInteger bigNSubOne = bigN.subtract( BigInteger.ONE );
		BigInteger bigD = BigInteger.valueOf( d );
		for ( long a: numberForLongPrime ) {
			if ( a >= n ) {
				return true;
			}
			BigInteger t = bigD;
			BigInteger y = BigInteger.valueOf( a ).modPow( t, bigN );
			while ( t.compareTo( bigNSubOne ) == -1 && !y.equals( BigInteger.ONE ) && !y.equals( bigNSubOne ) ) {
				y = y.multiply( y ).mod( bigN );
				t = t.shiftLeft( 1 );
			}
			if ( !y.equals( bigNSubOne ) && (t.intValue()&1) == 0 ) {
				return false;
			}
		}
		return true;
	}
	static int[] primes ( int num ) {
		if ( num < 2 ) {
			return new int[0];
		}
		BitSet numbers = new BitSet( num + 1 );
		numbers.set( 2, num + 1 );
		int limit = ( int )Math.sqrt( num );
		for ( int i = 2; i <= limit; ++i ) {
			if ( numbers.get( i ) ) {
				for ( int j = i * i; j <= num; j += i ) {
					if ( numbers.get(j) ) {
						numbers.clear( j );
					}
				}
			}
		}
		int[] answer = new int[numbers.cardinality()];
		int i = 2, index = 0;
		do {
			i = numbers.nextSetBit( i );
			answer[index++] = i++;
		} while ( index != answer.length );
		return answer;
	}
	static long pow ( long a, long b ) {
		long ans = 1;
		while ( b > 0 ) {
			if ( ( b & 1 ) == 1 ) {
				ans *= a;
			}
			a *= a;
			b >>= 1;
		}
		return ans;
	}
	static long modPow ( long a, long b, long mod ) {
		long ans = 1;
		a %= mod;
		while ( b > 0 ) {
			if ( ( b & 1 ) == 1 ) {
				ans *= a;
			}
			ans %= mod;
			a *= a;
			a %= mod;
			b >>= 1;
		}
		return ans;
	}
	static long fact ( int N ) {
		long ans = 1;
		for ( int i = 2; i <= N; ++i ) {
			ans *= i;
		}
		return ans;
	}
	static long modFact ( int N, long mod ) {
		long ans = 1;
		for ( int i = 2; i <= N; ++i ) {
			ans *= i;
			ans %= mod;
		}
		return ans;
	}
	static long combi ( long n, long r ) {
		if ( r < 0 || n < r ) {
			return 0;
		}
		long ans = 1;
		r = Math.min( n - r, r );
		for ( int i = 0; i < r; ++i ) {
			ans *= n - i;
			ans /= i + 1;
		}
		return ans;
	}
	static long modCombi ( long n, long r, long mod ) {
		if ( r < 0 || n < r ) {
			return 0;
		}
		long ans = 1;
		r = Math.min( n - r, r );
		for ( int i = 0; i < r; ++i ) {
			ans *= ( n - i ) % mod;
			ans %= mod;
			ans *= modPow( i + 1, mod - 2, mod );
			ans %= mod;
		}
		return ans;
	}
	static boolean rangeCheck ( int num, int l, int r ) {
		return l <= num && num < r;
	}
	static boolean rangeCheck ( long num, long l, long r ) {
		return l <= num && num < r;
	}
	static boolean rangeCheck ( double num, double l, double r ) {
		return l <= num && num < r;
	}
	static <E extends Comparable<E>> boolean rangeCheck ( E num, E l, E r ) {
		return 0 <= l.compareTo( num ) && 0 < num.compareTo( r );
	}
	static boolean rangeCheckOpen ( int num, int l, int r ) {
		return l < num && num < r;
	}
	static boolean rangeCheckOpen ( long num, long l, long r ) {
		return l < num && num < r;
	}
	static boolean rangeCheckOpen ( double num, double l, double r ) {
		return l < num && num < r;
	}
	static <E extends Comparable<E>> boolean rangeCheckOpen ( E num, E l, E r ) {
		return 0 < l.compareTo( num ) && 0 < num.compareTo( r );
	}
	static boolean rangeCheckClose ( int num, int l, int r ) {
		return l <= num && num <= r;
	}
	static boolean rangeCheckClose ( long num, long l, long r ) {
		return l <= num && num <= r;
	}
	static boolean rangeCheckClose ( double num, double l, double r ) {
		return l <= num && num <= r;
	}
	static <E extends Comparable<E>> boolean rangeCheckClose ( E num, E l, E r ) {
		return 0 <= l.compareTo( num ) && 0 <= num.compareTo( r );
	}
}
class Searcher {
	static int CYCLE_COUNT = Double.MAX_EXPONENT + 53;
	static int downSearch ( int[] array, int value ) {
		int a = 0, b = array.length - 1, ans = -1, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( array[c] > value ) {
				b = c - 1;
			}
			else {
				a = ( ans = c ) + 1;
			}
		}
		return ans;
	}
	static int downSearch ( long[] array, long value ) {
		int a = 0, b = array.length - 1, ans = -1, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( array[c] > value ) {
				b = c - 1;
			}
			else {
				a = ( ans = c ) + 1;
			}
		}
		return ans;
	}
	static int downSearch ( double[] array, double value ) {
		int a = 0, b = array.length - 1, ans = -1, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( array[c] > value ) {
				b = c - 1;
			}
			else {
				a = ( ans = c ) + 1;
			}
		}
		return ans;
	}
	static int downSearch ( char[] array, int value ) {
		int a = 0, b = array.length - 1, ans = -1, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( array[c] > value ) {
				b = c - 1;
			}
			else {
				a = ( ans = c ) + 1;
			}
		}
		return ans;
	}
	static <E extends Comparable<E>> int downSearch ( E[] array, E value ) {
		int a = 0, b = array.length - 1, ans = -1, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( array[c].compareTo( value ) > 0 ) {
				b = c - 1;
			}
			else {
				a = ( ans = c ) + 1;
			}
		}
		return ans;
	}
	static <E extends Comparable<E>> int downSearch ( List<E> list, E value ) {
		int a = 0, b = list.size() - 1, ans = -1, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( list.get( c ).compareTo( value ) > 0 ) {
				b = c - 1;
			}
			else {
				a = ( ans = c ) + 1;
			}
		}
		return ans;
	}
	static int downSearch ( int a, int b, int value, IntUnaryOperator func ) {
		int ans = a - 1, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( func.applyAsInt( c ) > value ) {
				b = c - 1;
			}
			else {
				a = ( ans = c ) + 1;
			}
		}
		return ans;
	}
	static long downSearch ( long a, long b, long value, LongUnaryOperator func ) {
		long ans = a - 1, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( func.applyAsLong( c ) > value ) {
				b = c - 1;
			}
			else {
				a = ( ans = c ) + 1;
			}
		}
		return ans;
	}
	static double search ( double a, double b, double value, DoubleUnaryOperator func ) {
		double ans = a - Math.abs( a ), c;
		for ( int $ = 0; $ < CYCLE_COUNT; ++$ ) {
			c = ( a + b ) / 2;
			if ( func.applyAsDouble( c ) > value ) {
				b = c;
			}
			else {
				a = ( ans = c );
			}
		}
		return ans;
	}
	static int upSearch ( int[] array, int value ) {
		int a = 0, b = array.length - 1, ans = array.length, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( array[c] >= value ) {
				b = ( ans = c ) - 1;
			}
			else {
				a = c + 1;
			}
		}
		return ans;
	}
	static int upSearch ( long[] array, long value ) {
		int a = 0, b = array.length - 1, ans = array.length, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( array[c] >= value ) {
				b = ( ans = c ) - 1;
			}
			else {
				a = c + 1;
			}
		}
		return ans;
	}
	static int upSearch ( double[] array, double value ) {
		int a = 0, b = array.length - 1, ans = array.length, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( array[c] >= value ) {
				b = ( ans = c ) - 1;
			}
			else {
				a = c + 1;
			}
		}
		return ans;
	}
	static int upSearch ( char[] array, char value ) {
		int a = 0, b = array.length - 1, ans = array.length, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( array[c] >= value ) {
				b = ( ans = c ) - 1;
			}
			else {
				a = c + 1;
			}
		}
		return ans;
	}
	static <E extends Comparable<E>> int upSearch ( E[] array, E value ) {
		int a = 0, b = array.length - 1, ans = array.length, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( array[c].compareTo( value ) >= 0 ) {
				b = ( ans = c ) - 1;
			}
			else {
				a = c + 1;
			}
		}
		return ans;
	}
	static <E extends Comparable<E>> int upSearch ( List<E> list, E value ) {
		int a = 0, b = list.size() - 1, ans = list.size(), c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( list.get( c ).compareTo( value ) >= 0 ) {
				b = ( ans = c ) - 1;
			}
			else {
				a = c + 1;
			}
		}
		return ans;
	}
	static int upSearch ( int a, int b, int value, IntUnaryOperator func ) {
		int ans = b + 1, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( func.applyAsInt( c ) >= value ) {
				b = ( ans = c ) - 1;
			}
			else {
				a = c + 1;
			}
		}
		return ans;
	}
	static long upSearch ( long a, long b, long value, LongUnaryOperator func ) {
		long ans = b + 1, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( func.applyAsLong( c ) >= value ) {
				b = ( ans = c ) - 1;
			}
			else {
				a = c + 1;
			}
		}
		return ans;
	}
	static int underSearch ( int[] array, int value ) {
		int a = 0, b = array.length - 1, ans = -1, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( array[c] >= value ) {
				b = c - 1;
			}
			else {
				a = ( ans = c ) + 1;
			}
		}
		return ans;
	}
	static int underSearch ( long[] array, long value ) {
		int a = 0, b = array.length - 1, ans = -1, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( array[c] >= value ) {
				b = c - 1;
			}
			else {
				a = ( ans = c ) + 1;
			}
		}
		return ans;
	}
	static int underSearch ( double[] array, double value ) {
		int a = 0, b = array.length - 1, ans = -1, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( array[c] >= value ) {
				b = c - 1;
			}
			else {
				a = ( ans = c ) + 1;
			}
		}
		return ans;
	}
	static int underSearch ( char[] array, char value ) {
		int a = 0, b = array.length - 1, ans = -1, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( array[c] >= value ) {
				b = c - 1;
			}
			else {
				a = ( ans = c ) + 1;
			}
		}
		return ans;
	}
	static <E extends Comparable<E>> int underSearch ( E[] array, E value ) {
		int a = 0, b = array.length - 1, ans = -1, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( array[c].compareTo( value ) >= 0 ) {
				b = c - 1;
			}
			else {
				a = ( ans = c ) + 1;
			}
		}
		return ans;
	}
	static <E extends Comparable<E>> int underSearch ( List<E> list, E value ) {
		int a = 0, b = list.size() - 1, ans = -1, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( list.get( c ).compareTo( value ) >= 0 ) {
				b = c - 1;
			}
			else {
				a = ( ans = c ) + 1;
			}
		}
		return ans;
	}
	static int underSearch ( int a, int b, int value, IntUnaryOperator func ) {
		int ans = a - 1, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( func.applyAsInt( c ) >= value ) {
				b = c - 1;
			}
			else {
				a = ( ans = c ) + 1;
			}
		}
		return ans;
	}
	static long underSearch ( long a, long b, long value, LongUnaryOperator func ) {
		long ans = a - 1, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( func.applyAsLong( c ) >= value ) {
				b = c - 1;
			}
			else {
				a = ( ans = c ) + 1;
			}
		}
		return ans;
	}
	static int overSearch ( int[] array, int value ) {
		int a = 0, b = array.length - 1, ans = array.length, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( array[c] > value ) {
				b = ( ans = c ) - 1;
			}
			else {
				a = c + 1;
			}
		}
		return ans;
	}
	static int overSearch ( long[] array, long value ) {
		int a = 0, b = array.length - 1, ans = array.length, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( array[c] > value ) {
				b = ( ans = c ) - 1;
			}
			else {
				a = c + 1;
			}
		}
		return ans;
	}
	static int overSearch ( double[] array, double value ) {
		int a = 0, b = array.length - 1, ans = array.length, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( array[c] > value ) {
				b = ( ans = c ) - 1;
			}
			else {
				a = c + 1;
			}
		}
		return ans;
	}
	static int overSearch ( char[] array, char value ) {
		int a = 0, b = array.length - 1, ans = array.length, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( array[c] > value ) {
				b = ( ans = c ) - 1;
			}
			else {
				a = c + 1;
			}
		}
		return ans;
	}
	static <E extends Comparable<E>> int overSearch ( E[] array, E value ) {
		int a = 0, b = array.length - 1, ans = array.length, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( array[c].compareTo( value ) > 0 ) {
				b = ( ans = c ) - 1;
			}
			else {
				a = c + 1;
			}
		}
		return ans;
	}
	static <E extends Comparable<E>> int overSearch ( List<E> list, E value ) {
		int a = 0, b = list.size() - 1, ans = list.size(), c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( list.get( c ).compareTo( value ) > 0 ) {
				b = ( ans = c ) - 1;
			}
			else {
				a = c + 1;
			}
		}
		return ans;
	}
	static int overSearch ( int a, int b, int value, IntUnaryOperator func ) {
		int ans = b + 1, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( func.applyAsInt( c ) > value ) {
				b = ( ans = c ) - 1;
			}
			else {
				a = c + 1;
			}
		}
		return ans;
	}
	static long overSearch ( long a, long b, long value, LongUnaryOperator func ) {
		long ans = b + 1, c;
		while ( a - b < 1 ) {
			c = ( a + b ) / 2;
			if ( func.applyAsLong( c ) > value ) {
				b = ( ans = c ) - 1;
			}
			else {
				a = c + 1;
			}
		}
		return ans;
	}
}
class BIT {
	int size;
	long[] tree;
	BIT ( int n ) {
		size = n;
		tree = new long[n + 1];
	}
	long sum ( int i ) {
		long sum = 0;
		while ( i > 0 ) {
			sum += tree[i];
			i ^= i & ( -i );
		}
		return sum;
	}
	void add ( int i, long x ) {
		while ( i <= size ) {
			tree[i] += x;
			i += i & ( -i );
		}
	}
	void clear () {
		Arrays.fill( tree, 0L );
	}
}
class RollingHash implements Comparable<RollingHash> {
	static long BASE = new Random().nextInt( 1000 ) + Character.MAX_VALUE + 1;
	static long MASK30 = ( 1L << 30 ) - 1;
	static long MASK31 = ( 1L << 31 ) - 1;
	static long MOD = ( 1L << 61 ) - 1;
	static long MASK61 = MOD;
	long[] hash;
	String string;
	RollingHash ( String str ) {
		string = str;
		hash = new long[str.length() + 1];
		roll();
	}
	void roll () {
		int len = string.length();
		for ( int i = 1; i <= len; ++i ) {
			hash[i] = multiply( hash[i - 1], BASE ) + string.charAt( i - 1 ) - ' ' + 1;
			if ( MOD <= hash[i] ) {
				hash[i] -= MOD;
			}
		}
	}
	static long multiply ( long a, long b ) {
		long au = a >> 31;
		long ad = a & MASK31;
		long bu = b >> 31;
		long bd = b & MASK31;
		long mid = ad * bu + au * bd;
		long midu = mid >> 30;
		long midd = mid & MASK30;
		return mod( au * bu * 2 + midu + ( midd << 31 ) + ad * bd );
	}
	static long mod ( long x ) {
		long xu = x >> 61;
		long xd = x & MASK61;
		long ans = xu + xd;
		if ( MOD <= ans ) {
			ans -= MOD;
		}
		return ans;
	}
	long getHash ( int l, int r ) {
		return ( hash[r] - multiply( hash[l], modBasePow( r - l ) ) + MOD ) % MOD;
	}
	static long modBasePow ( long b ) {
		long ans = 1;
		long a = BASE;
		while ( b > 0 ) {
			if ( ( b & 1 ) == 1 ) {
				ans = multiply( ans, a );
			}
			a = multiply( a, a );
			b >>= 1;
		}
		return ans;
	}
	boolean equals ( RollingHash rh, int l1, int r1, int l2, int r2 ) {
		if ( r1 - l1 != r2 - l2 ) {
			return false;
		}
		return getHash( l1, r1 ) == rh.getHash( l2, r2 );
	}
	int length () {
		return string.length();
	}
	public int hashCode () {
		return string.hashCode();
	}
	public String toString () {
		return string;
	}
	public boolean equals ( Object o ) {
		if ( o instanceof RollingHash rh ) {
			return equals( rh, 0, length(), 0, rh.length() );
		}
		return false;
	}
	public int compareTo ( RollingHash rh ) {
		return string.compareTo( rh.toString() );
	}
	int compareTo ( String str ) {
		return string.compareTo( str );
	}
	char charAt ( int i ) {
		return string.charAt( i );
	}
	int compareToIgnoreCase ( RollingHash rh ) {
		return string.compareToIgnoreCase( rh.toString() );
	}
	int compareToIgnoreCase ( String str ) {
		return string.compareToIgnoreCase( str );
	}
	void concat ( RollingHash rh ) {
		concat( rh.toString() );
	}
	void concat ( String str ) {
		string = string.concat( str );
		hash = new long[string.length() + 1];
		roll();
	}
	boolean contains ( RollingHash rh ) {
		long hash = rh.getHash( 0, rh.length() );
		int len = length() - rh.length();
		for ( int i = 0; i <= len; ++i ) {
			if ( hash == getHash( i, rh.length() + i ) ) {
				return true;
			}
		}
		return false;
	}
	boolean contains ( String str ) {
		return indexOf( str ) != -1;
	}
	int indexOf ( int ch ) {
		return indexOf( ch, 0 );
	}
	int indexOf ( int ch, int fromIndex ) {
		int len = length();
		for ( int i = fromIndex; i < len; ++i ) {
			if ( string.charAt( i ) == ch ) {
				return i;
			}
		}
		return -1;
	}
	int indexOf ( String str ) {
		return indexOf( str, 0 );
	}
	int indexOf ( String str, int fromIndex ) {
		long hash = 0;
		for ( char c: str.toCharArray() ) {
			hash = multiply( hash, BASE ) + c - ' ' + 1;
			if ( MOD <= hash ) {
				hash -= MOD;
			}
		}
		int len = length() - str.length();
		for ( int i = fromIndex; i <= len; ++i ) {
			if ( hash == getHash( i, str.length() + i ) ) {
				return i;
			}
		}
		return -1;
	}
	boolean isEmpty () {
		return length() == 0;
	}
	int lastIndexOf ( int ch, int fromIndex ) {
		for ( int i = fromIndex; i >= 0; --i ) {
			if ( string.charAt( i ) == ch ) {
				return i;
			}
		}
		return -1;
	}
	int lastIndexOf ( int ch ) {
		return lastIndexOf( ch, length() - 1 );
	}
}
@SuppressWarnings( "unchecked" )
abstract class SegmentTree<E> {
	int N, size;
	E def;
	Object[] node;
	SegmentTree ( int n, E def, boolean include ) {
		int num = 2;
		while ( num < n << 1 ) {
			num <<= 1;
		}
		N = num;
		size = num >> 1 - ( include ? 1 : 0 );
		node = new Object[N];
		this.def = def;
		Arrays.fill( node, this.def );
	}
	SegmentTree ( E[] arr, E def, boolean include ) {
		int num = 2;
		while ( num < arr.length << 1 ) {
			num <<= 1;
		}
		N = num;
		size = num >> 1 - ( include ? 1 : 0 );
		node = new Object[N];
		this.def = def;
		System.arraycopy( arr, 0, node, N >> 1, arr.length );
		for ( int i = arr.length + ( N >> 1 ); i < N; i++ ) {
			node[i] = def;
		}
		updateAll();
	}
	SegmentTree ( int n, E def ) {
		this( n, def, false );
	}
	void updateAll () {
		for ( int i = ( N >> 1 ) - 1; i > 0; i-- ) {
			node[i] = function( ( E )node[i << 1], ( E )node[( i << 1 ) + 1] );
		}
	}
	void update ( int n, E value ) {
		n += size;
		node[n] = value;
		n >>= 1;
		while ( n > 0 ) {
			node[n] = function( ( E )node[n << 1], ( E )node[( n << 1 ) + 1] );
			n >>= 1;
		}
	}
	E get ( int a ) {
		return ( E )node[a + size];
	}
	E answer () {
		return ( E )node[1];
	}
	E query ( int l, int r ) {
		l += size;
		r += size;
		E answer = def;
		while ( l > 0 && r > 0 && l <= r ) {
			if ( l % 2 == 1 ) {
				answer = function( ( E )node[l++], answer );
			}
			l >>= 1;
			if ( r % 2 == 0 ) {
				answer = function( answer, ( E )node[r--] );
			}
			r >>= 1;
		}
		return answer;
	}
	abstract E function ( E a, E b );
}
class UnionFind {
	int[] par, rank, size, path;
	int count;
	UnionFind ( int N ) {
		count = N;
		par = new int[N];
		rank = new int[N];
		size = new int[N];
		path = new int[N];
		Arrays.fill( par, -1 );
		Arrays.fill( size, 1 );
	}
	int root ( int ind ) {
		if ( par[ind] == -1 ) {
			return ind;
		}
		else {
			return par[ind] = root( par[ind] );
		}
	}
	boolean isSame ( int x, int y ) {
		return root( x ) == root( y );
	}
	boolean unite ( int x, int y ) {
		int rx = root( x );
		int ry = root( y );
		++path[rx];
		if ( rx == ry ) {
			return false;
		}
		if ( rank[rx] < rank[ry] ) {
			int temp = rx;
			rx = ry;
			ry = temp;
		}
		par[ry] = rx;
		if ( rank[rx] == rank[ry] ) {
			++rank[rx];
		}
		path[rx] += path[ry];
		size[rx] += size[ry];
		--count;
		return true;
	}
	int groupCount () {
		return count;
	}
	int pathCount ( int x ) {
		return path[root( x )];
	}
	int size ( int x ) {
		return size[root( x )];
	}
}
class SimpleScanner {
	int BUFF_SIZE = 1 << 17;
	InputStream is;
	byte[] buff;
	int point, length;
	SimpleScanner ( InputStream is ) {
		this.is = is;
		buff = new byte[BUFF_SIZE];
		point = length = 0;
	}
	void reload () {
		do {
			try {
				length = is.read( buff, point = 0, BUFF_SIZE );
			} catch ( IOException e ) {
				e.printStackTrace();
				System.exit( 1 );
			}
		} while ( length == -1 );
	}
	byte read () {
		if ( point == length ) {
			reload();
		}
		return buff[point++];
	}
	byte nextByte () {
		byte c = read();
		while ( c <= ' ' ) {
			c = read();
		}
		return c;
	}
	int nextInt () {
		int ans = 0;
		byte c = nextByte();
		boolean negate = c == '-';
		if ( !MathFunction.rangeCheckClose( c, '0', '9' ) ) {
			c = read();
		}
		while ( MathFunction.rangeCheckClose( c, '0', '9' ) ) {
			ans = ans * 10 + c - '0';
			c = read();
		}
		return negate ? -ans : ans;
	}
	long nextLong () {
		long ans = 0;
		byte c = nextByte();
		boolean negate = c == '-';
		if ( !MathFunction.rangeCheckClose( c, '0', '9' ) ) {
			c = read();
		}
		while ( MathFunction.rangeCheckClose( c, '0', '9' ) ) {
			ans = ans * 10L + c - '0';
			c = read();
		}
		return negate ? -ans : ans;
	}
	char nextChar () {
		return ( char )nextByte();
	}
	String next () {
		StringBuilder ans = new StringBuilder();
		byte c = nextByte();
		while ( c > ' ' ) {
			ans.append( ( char )c );
			c = read();
		}
		return ans.toString();
	}
	BigInteger nextBigInteger () {
		return new BigInteger( next() );
	}
	byte[] nextByte ( int n ) {
		byte[] ans = new byte[n];
		for ( int i = 0; i < n; ++i ) {
			ans[i] = nextByte();
		}
		return ans;
	}
	int[] nextInt ( int n ) {
		int[] ans = new int[n];
		for ( int i = 0; i < n; ++i ) {
			ans[i] = nextInt();
		}
		return ans;
	}
	long[] nextLong ( int n ) {
		long[] ans = new long[n];
		for ( int i = 0; i < n; ++i ) {
			ans[i] = nextLong();
		}
		return ans;
	}
	String[] next ( int n ) {
		String[] ans = new String[n];
		for ( int i = 0; i < n; ++i ) {
			ans[i] = next();
		}
		return ans;
	}
	byte[][] nextByte ( int n, int m ) {
		byte[][] ans = new byte[n][];
		for ( int i = 0; i < n; ++i ) {
			ans[i] = nextByte( m );
		}
		return ans;
	}
	int[][] nextInt ( int n, int m ) {
		int[][] ans = new int[n][];
		for ( int i = 0; i < n; ++i ) {
			ans[i] = nextInt( m );
		}
		return ans;
	}
	long[][] nextLong ( int n, int m ) {
		long[][] ans = new long[n][];
		for ( int i = 0; i < n; ++i ) {
			ans[i] = nextLong( m );
		}
		return ans;
	}
	String[][] next ( int n, int m ) {
		String[][] ans = new String[n][];
		for ( int i = 0; i < n; ++i ) {
			ans[i] = next( m );
		}
		return ans;
	}
	char[] nextCharArray () {
		return next().toCharArray();
	}
	char[][] nextCharArray ( int n ) {
		char[][] ans = new char[n][];
		for ( int i = 0; i < n; ++i ) {
			ans[i] = nextCharArray();
		}
		return ans;
	}
	int[][] nextGraph ( int N, int M ) {
		if ( M == 0 ) {
			return new int[N + 1][0];
		}
		int[][] ans = new int[N + 1][];
		int[] count = new int[N + 1];
		int[][] path = nextInt( M, 2 );
		for ( int[] temp: path ) {
			++count[temp[0]];
			++count[temp[1]];
		}
		for ( int i = 1; i <= N; ++i ) {
			ans[i] = new int[count[i]];
		}
		for ( int[] temp: path ) {
			ans[temp[0]][--count[temp[0]]] = temp[1];
			ans[temp[1]][--count[temp[1]]] = temp[0];
		}
		ans[0] = new int[0];
		return ans;
	}
	Point nextPoint () {
		return new Point( nextInt(), nextInt() );
	}
	Point[] nextPoint ( int n ) {
		Point[] ans = new Point[n];
		for ( int i = 0; i < n; ++i ) {
			ans[i] = nextPoint();
		}
		return ans;
	}
	public void close () {
		try {
			is.close();
		} catch ( IOException e ) {
			e.printStackTrace();
			System.exit( 1 );
		}
	}
}
class SimpleOutputStream extends FilterOutputStream {
	byte buf[];
	int count;
	SimpleOutputStream(OutputStream out) {
		this(out, 1<<17);
	}
	SimpleOutputStream(OutputStream out, int size) {
		super(out);
		if (size <= 0) {
			throw new IllegalArgumentException("Buffer size <= 0");
		}
		buf = new byte[size];
	}
	void flushBuffer() throws IOException {
		if (count > 0) {
			out.write(buf, 0, count);
			count = 0;
		}
	}
	public void write(int b) throws IOException {
		if (count >= buf.length) {
			flushBuffer();
		}
		buf[count++] = (byte)b;
	}
	public void write(byte b[], int off, int len) throws IOException {
		if (len >= buf.length) {
			flushBuffer();
			out.write(b, off, len);
			return;
		}
		if (len > buf.length - count) {
			flushBuffer();
		}
		System.arraycopy(b, off, buf, count, len);
		count += len;
	}
	public void flush() throws IOException {
		flushBuffer();
		out.flush();
	}
}
class SimpleWriter implements Appendable, Closeable, Flushable, AutoCloseable{
	Writer out;
	boolean autoFlush;
	boolean trouble = false;
	Formatter formatter;
	PrintStream psOut = null;
	static Charset toCharset ( String csn ) {
		if ( csn == null ) {
			throw new NullPointerException( "charsetName" );
		}
		try {
			return Charset.forName( csn );
		} catch ( IllegalCharsetNameException |
				  UnsupportedCharsetException e ) {
			e.printStackTrace();
			System.exit( 1 );
			return null;
		}
	}
	SimpleWriter ( Writer out ) {
		this( out, false );
	}
	SimpleWriter ( Writer out, boolean autoFlush ) {
		this.out = out;
		this.autoFlush = autoFlush;
	}
	SimpleWriter ( OutputStream out ) {
		this( out, false );
	}
	SimpleWriter ( OutputStream out, boolean autoFlush ) {
		this(out, autoFlush, Charset.defaultCharset());
	}
	SimpleWriter(OutputStream out, boolean autoFlush, Charset charset) {
		this(new BufferedWriter(new OutputStreamWriter(new SimpleOutputStream(out), charset)), autoFlush);
		if (out instanceof PrintStream) {
			psOut = (PrintStream) out;
		}
	}
	void ensureOpen () throws IOException {
		if ( out == null ) {
			throw new IOException( "Stream closed" );
		}
	}
	public void flush () {
		try {
			ensureOpen();
			out.flush();
		} catch ( IOException x ) {
			trouble = true;
		}
	}
	public void close () {
		try {
			if ( out == null ) {
				return;
			}
			out.close();
			out = null;
		} catch ( IOException x ) {
			trouble = true;
		}
	}
	boolean checkError () {
		if ( out != null ) {
			flush();
		}
		else if ( psOut != null ) {
			return psOut.checkError();
		}
		return trouble;
	}
	void setError () {
		trouble = true;
	}
	void clearError () {
		trouble = false;
	}
	void write ( int c ) {
		try {
			ensureOpen();
			out.write( c );
		} catch ( InterruptedIOException x ) {
			Thread.currentThread().interrupt();
		} catch ( IOException x ) {
			trouble = true;
		}
	}
	void write ( char[] buf, int off, int len ) {
		try {
			ensureOpen();
			out.write( buf, off, len );
		} catch ( InterruptedIOException x ) {
			Thread.currentThread().interrupt();
		} catch ( IOException x ) {
			trouble = true;
		}
	}
	void write ( char[] buf ) {
		write( buf, 0, buf.length );
	}
	void write ( String s, int off, int len ) {
		try {
			ensureOpen();
			out.write( s, off, len );
		} catch ( InterruptedIOException x ) {
			Thread.currentThread().interrupt();
		} catch ( IOException x ) {
			trouble = true;
		}
	}
	void write ( String s ) {
		write( s, 0, s.length() );
	}
	void newLine () {
		try {
			ensureOpen();
			out.write( System.lineSeparator() );
			if ( autoFlush ) {
				out.flush();
			}
		} catch ( InterruptedIOException x ) {
			Thread.currentThread().interrupt();
		} catch ( IOException x ) {
			trouble = true;
		}
	}
	void print ( boolean b ) {
		write( b ? "true" : "false" );
	}
	void print ( char c ) {
		write( c );
	}
	void print ( int i ) {
		write( String.valueOf( i ) );
	}
	void print ( long l ) {
		write( String.valueOf( l ) );
	}
	void print ( float f ) {
		write( String.valueOf( f ) );
	}
	void print ( double d ) {
		write( String.valueOf( d ) );
	}
	void print ( char[] s ) {
		write( s );
	}
	void print ( String s ) {
		write( s );
	}
	void print ( Object obj ) {
		write( obj.toString() );
	}
	void println () {
		newLine();
	}
	void println ( boolean x ) {
		print( x );
		println();
	}
	void println ( char x ) {
		print( x );
		println();
	}
	void println ( int x ) {
		print( x );
		println();
	}
	void println ( long x ) {
		print( x );
		println();
	}
	void println ( float x ) {
		print( x );
		println();
	}
	void println ( double x ) {
		print( x );
		println();
	}
	void println ( char[] x ) {
		print( x );
		println();
	}
	void println ( String x ) {
		print( x );
		println();
	}
	void println ( Object x ) {
		print( x.toString() );
		println();
	}
	SimpleWriter printf ( String format, Object... args ) {
		return format( format, args );
	}
	SimpleWriter printf ( Locale l, String format, Object... args ) {
		return format( l, format, args );
	}
	SimpleWriter format ( String format, Object... args ) {
		try {
			ensureOpen();
			if ( ( formatter == null )
				 || ( formatter.locale() != Locale.getDefault() ) ) {
				formatter = new Formatter( this );
			}
			formatter.format( Locale.getDefault(), format, args );
			if ( autoFlush ) {
				out.flush();
			}
		} catch ( InterruptedIOException x ) {
			Thread.currentThread().interrupt();
		} catch ( IOException x ) {
			trouble = true;
		}
		return this;
	}
	SimpleWriter format ( Locale l, String format, Object... args ) {
		try {
			ensureOpen();
			if ( ( formatter == null ) || ( formatter.locale() != l ) ) {
				formatter = new Formatter( this, l );
			}
			formatter.format( l, format, args );
			if ( autoFlush ) {
				out.flush();
			}
		} catch ( InterruptedIOException x ) {
			Thread.currentThread().interrupt();
		} catch ( IOException x ) {
			trouble = true;
		}
		return this;
	}
	public SimpleWriter append ( CharSequence csq ) {
		write( String.valueOf( csq ) );
		return this;
	}
	public SimpleWriter append ( CharSequence csq, int start, int end ) {
		if ( csq == null ) {
			csq = "null";
		}
		return append( csq.subSequence( start, end ) );
	}
	public SimpleWriter append ( char c ) {
		write( c );
		return this;
	}
	void println ( int[] array ) {
		println( array, ' ' );
	}
	void println ( int[] array, String str ) {
		print( array[0] );
		for ( int i = 1; i < array.length; ++i ) {
			print( str );
			print( array[i] );
		}
		println();
	}
	void println ( int[] array, char c ) {
		print( array[0] );
		for ( int i = 1; i < array.length; ++i ) {
			print( c );
			print( array[i] );
		}
		println();
	}
	void println ( int[][] array ) {
		println( array, ' ' );
	}
	void println ( int[][] arrays, String str ) {
		for ( int[] array: arrays ) {
			println( array, str );
		}
	}
	void println ( int[][] arrays, char c ) {
		for ( int[] array: arrays ) {
			println( array, c );
		}
	}
	void println ( long[] array ) {
		println( array, ' ' );
	}
	void println ( long[] array, String str ) {
		print( array[0] );
		for ( int i = 1; i < array.length; ++i ) {
			print( str );
			print( array[i] );
		}
		println();
	}
	void println ( long[] array, char c ) {
		print( array[0] );
		for ( int i = 1; i < array.length; ++i ) {
			print( c );
			print( array[i] );
		}
		println();
	}
	void println ( long[][] array ) {
		println( array, ' ' );
	}
	void println ( long[][] arrays, String str ) {
		for ( long[] array: arrays ) {
			println( array, str );
		}
	}
	void println ( long[][] arrays, char c ) {
		for ( long[] array: arrays ) {
			println( array, c );
		}
	}
	void println ( double[] array ) {
		println( array, ' ' );
	}
	void println ( double[] array, String str ) {
		print( array[0] );
		for ( int i = 1; i < array.length; ++i ) {
			print( str );
			print( array[i] );
		}
		println();
	}
	void println ( double[] array, char c ) {
		print( array[0] );
		for ( int i = 1; i < array.length; ++i ) {
			print( c );
			print( array[i] );
		}
		println();
	}
	void println ( double[][] array ) {
		println( array, ' ' );
	}
	void println ( double[][] arrays, String str ) {
		for ( double[] array: arrays ) {
			println( array, str );
		}
	}
	void println ( double[][] arrays, char c ) {
		for ( double[] array: arrays ) {
			println( array, c );
		}
	}
	void println ( char[] cs, String str ) {
		print( cs[0] );
		for ( int i = 1; i < cs.length; ++i ) {
			print( str );
			print( cs[i] );
		}
		println();
	}
	void println ( char[] cs, char c ) {
		print( cs[0] );
		for ( int i = 1; i < cs.length; ++i ) {
			print( c );
			print( cs[i] );
		}
		println();
	}
	void println ( char[][] cs ) {
		for ( char[] c: cs ) {
			println( c );
		}
	}
	void println ( char[][] cs, String str ) {
		for ( char[] c: cs ) {
			println( c, str );
		}
	}
	void println ( char[][] cs, char c ) {
		for ( char[] cc: cs ) {
			println( cc, c );
		}
	}
	<E> void println ( E[] array ) {
		println( array, ' ' );
	}
	<E> void println ( E[] array, String str ) {
		print( array[0] );
		for ( int i = 1; i < array.length; ++i ) {
			print( str );
			print( array[i] );
		}
		println();
	}
	<E> void println ( E[] array, char c ) {
		print( array[0] );
		for ( int i = 1; i < array.length; ++i ) {
			print( c );
			print( array[i] );
		}
		println();
	}
	<E> void println ( E[][] arrays ) {
		println( arrays, ' ' );
	}
	<E> void println ( E[][] arrays, String str ) {
		for ( E[] array: arrays ) {
			println( array, str );
		}
	}
	<E> void println ( E[][] arrays, char c ) {
		for ( E[] array: arrays ) {
			println( array, c );
		}
	}
	<E> void println ( List<E> list ) {
		println( list, ' ' );
	}
	<E> void println ( List<E> list, String str ) {
		if ( list.size() == 0 ) {
			println();
			return;
		}
		print( list.get( 0 ) );
		for ( int i = 1; i < list.size(); ++i ) {
			print( str );
			print( list.get( i ) );
		}
		println();
	}
	<E> void println ( List<E> list, char c ) {
		if ( list.size() == 0 ) {
			println();
			return;
		}
		print( list.get( 0 ) );
		for ( int i = 1; i < list.size(); ++i ) {
			print( c );
			print( list.get( i ) );
		}
		println();
	}
}