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.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[][] 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[][] 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> route ) { int[] count = new int[route.size()]; int pathCount = 0; for ( ArrayList path: route ) { for ( int point: path ) { ++pathCount; ++count[point]; } } ArrayDeque 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 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 > 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 > 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 > 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 > 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 > 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 > int downSearch ( List 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 > 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 > int upSearch ( List 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 > 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 > int underSearch ( List 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 > 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 > int overSearch ( List 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 { 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 { 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 ); } } void println ( E[] array ) { println( array, ' ' ); } void println ( E[] array, String str ) { print( array[0] ); for ( int i = 1; i < array.length; ++i ) { print( str ); print( array[i] ); } println(); } void println ( E[] array, char c ) { print( array[0] ); for ( int i = 1; i < array.length; ++i ) { print( c ); print( array[i] ); } println(); } void println ( E[][] arrays ) { println( arrays, ' ' ); } void println ( E[][] arrays, String str ) { for ( E[] array: arrays ) { println( array, str ); } } void println ( E[][] arrays, char c ) { for ( E[] array: arrays ) { println( array, c ); } } void println ( List list ) { println( list, ' ' ); } void println ( List 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(); } void println ( List 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(); } }