6 6
 1 4
 4 4
 3 3
 6 4
 6 3
 5 4
 5 6
 3 4
 1 3
 3 2
 5 5
 1 1
 2 1
 3 1
 3 5
 1 6
 6 5
 2 3
 4 3
 2 2
 3 6
 1 2
 6 1
 2 5
 4 5
 1 5
 6 2
 4 6
 5 1
 4 1
 5 2
 2 4
 2 6
 5 3

1/6
 1/2
 1/2
 2/3
 1/6
 1/6
 1/3
 1/6
 1/2
 2/3
 2/3
 1/3
 1/1
 5/6
 2/3
 1/3
 1/6
 1/6
 2/3
 1/2
 5/6
 1/6
 5/6
 1/6
 1/3
 1/3
 1/3
 1/6
 1/6
 1/3
 1/2
 1/3
 1/2
 1/6
 1/3

import java.io.*;
import java.util.*;
import java.util.regex.*;
import java.math.*;

import java.awt.geom.*;

/**
 * Google Code Jam problems solved (sometimes incorrectly) by Lev. A. Neiman.
 * @author Lev Neiman - lev.neiman@gmail.com
 * 
 */
public class Problems
{
	
	public interface Problem
	{
		public void solve(InputStream in, PrintStream out) throws Exception;
	}
	
	public interface facebook_problem extends Problem
	{
	}
	
	public interface acm_problem extends Problem
	{
		
	}
	
	public static class facebook_problems
	{
		public static class liarliar implements facebook_problem
		{
			
			void printPeople(Map<String, Set<String>> people)
			{
				for( String person : people.keySet() )
				{
					System.out.println( person + ":" );
					for( String liar : people.get( person ) )
					{
						System.out.println( "\t" + liar );
					}
				}
			}
			
			boolean find_liars(Map<String, Set<String>> people, Set<String> peeps, Set<String> liars, Set<String> truthers, String liar)
			{
				if (!peeps.contains( liar ))
					return false;
				System.out.println( "LIAR ! " + liar );
				peeps.remove( liar );
				liars.add( liar );
				for( String truthee : people.get( liar ) )
				{
					if (liars.contains( truthee ))
						return false;
					System.out.println( "TRUTHER ! " + truthee );
					truthers.add( truthee );
					peeps.remove( truthee );
					for( String liarz : people.get( truthee ) )
					{
						find_liars( people, peeps, liars, truthers, liarz );
					}
				}
				return true;
			}
			
			@Override
			public void solve(InputStream inFile, PrintStream out) throws Exception
			{
				String input = Util.Stream2String( inFile );
				StringTokenizer tokenizer = new StringTokenizer( input, " \n\r" );
				int n;
				Map<String, Set<String>> people = new HashMap<String, Set<String>>();
				Set<String> peeps = new HashSet<String>();
				n = Integer.parseInt( tokenizer.nextToken() );
				String first_liar = null;
				while (tokenizer.hasMoreTokens())
				{
					String name = tokenizer.nextToken();
					peeps.add( name );
					int m = Integer.parseInt( tokenizer.nextToken() );
					if (m > 0 && first_liar == null)
						first_liar = name;
					Set liars = new HashSet<String>();
					people.put( name, liars );
					for( int i = 0; i < m; ++i )
					{
						liars.add( tokenizer.nextToken() );
					}
				}
				//printPeople( people );
				Set<String> liars, goodies;
				liars = new HashSet<String>();
				goodies = new HashSet<String>();
				find_liars( people, peeps, liars, goodies, first_liar );
				while (peeps.size() > 0)
				{
					String liar = peeps.iterator().next();
					find_liars( people, peeps, liars, goodies, liar );
				}
				System.out.print( Math.max( liars.size(), goodies.size() ) + " " );
				System.out.print( Math.min( liars.size(), goodies.size() ) );
				
			}
			
		}
	}
	
	public static class Util
	{
		public static String Stream2String(InputStream is) throws IOException
		{
			String ret = "";
			while (is.available() > 0)
			{
				byte[] buff = new byte[is.available()];
				is.read( buff );
				String t = new String( buff );
				ret += t;
			}
			return ret;
		}
		
		public class Pair<T, U>
		{
			private final T first;
			private final U second;
			private transient final int hash;
			
			public Pair(T f, U s)
			{
				this.first = f;
				this.second = s;
				hash = (first == null ? 0 : first.hashCode() * 31) + (second == null ? 0 : second.hashCode());
			}
			
			public T getFirst()
			{
				return first;
			}
			
			public U getSecond()
			{
				return second;
			}
			
			@Override
			public int hashCode()
			{
				return hash;
			}
			
			@Override
			public boolean equals(Object oth)
			{
				if (this == oth)
				{
					return true;
				}
				if (oth == null || !(getClass().isInstance( oth )))
				{
					return false;
				}
				Pair<T, U> other = getClass().cast( oth );
				return (first == null ? other.first == null : first.equals( other.first ))
						&& (second == null ? other.second == null : second.equals( other.second ));
			}
			
		}
		
		/**
		 * Convert number in given base given as a string into base 10.
		 * @param numb
		 * @param base
		 * @return
		 */
		public static int convert(String numb, int base)
		{
			int ret = 0;
			int c = 0;
			for( int i = numb.length() - 1; i >= 0; --i )
			{
				ret += Math.pow( base, c ) * (numb.charAt( i ) - 48);
				++c;
			}
			return ret;
		}
		
		public static class Primes
		{
			static boolean[] primes = null;
			
			public static boolean[] prime_numbers()
			{
				if (primes != null)
					return primes;
				int lim = (int) 1e6;
				primes = new boolean[lim];
				for( int i = 0; i < lim; ++i )
					primes[i] = true;
				primes[0] = primes[1] = false;
				for( int k = 2; k < lim; ++k )
					if (primes[k])
						for( int c = 2; c * k < lim; ++c )
							primes[c * k] = false;
				
				return primes;
			}
			
		
			public void testPrimes()
			{
				boolean[] p = prime_numbers();
				for( int i = 0; i < 100; ++i )
					if (p[i])
						System.out.println( i );
			}
		}
		
		public static class Perm
		{
			public void test()
			{
				int[] t =
				{
						6, 2, 3, 3
				};
				boolean k = nextPerm( t );
				System.out.println( k );
				for( int i = 0; i < t.length; ++i )
					System.out.print( t[i] );
			}
			
			private static void swap(int[] p, int i, int j)
			{
				
				int t = p[i];
				p[i] = p[j];
				p[j] = t;
			}
			
			public static boolean nextPerm(int[] p)
			{
				
				int i;
				
				for( i = p.length - 1; i-- > 0 && p[i] > p[i + 1]; )
					;
				
				if (i < 0)
					return false;
				
				int j;
				
				for( j = p.length; --j > i && p[j] < p[i]; )
					;
				
				swap( p, i, j );
				
				for( j = p.length; --j > ++i; swap( p, i, j ) )
					;
				
				return true;
			}
			
			private static void print(int[] p)
			{
				
				for( int i = 0; i < p.length; ++i )
					System.out.print( p[i] + " " );
				System.out.println();
			}
			
			public static void main(String args[])
			{
				
				int[] p =
				{
						0, 1, 2, 3, 4, 5, 6, 7, 8
				};
				
				do
					print( p );
				while (nextPerm( p ));
			}
		}
		
	}
	
	public static class GCJ_Problems
	{
		public static class QualificationRound_2009
		{
			public static class WelcomeToCodeJam implements Problem
			{
				public static final String welcome = "welcome to code jam";
				
				long mem[][];
				
				long dfs(String text, int pos, int cons)
				{
					if (mem[pos][cons] != -1)
						return mem[pos][cons];
					if (cons == welcome.length() - 1 && text.charAt( pos ) == 'm')
						return 1;
					long ret = 0;
					for( int i = pos + 1; i < text.length(); ++i )
					{
						if (text.charAt( i ) == welcome.charAt( cons + 1 ))
						{
							//System.out.println( "yay");
							ret += dfs( text, i, cons + 1 ) % 10000;
						}
					}
					ret = ret % 10000;
					mem[pos][cons] = ret % 10000;
					return ret;
				}
				
				long solve(String text)
				{
					long ret = 0;
					mem = new long[text.length()][welcome.length()];
					for( int i = 0; i < mem.length; ++i )
						for( int j = 0; j < welcome.length(); ++j )
							mem[i][j] = -1;
					for( int i = 0; i < text.length(); ++i )
					{
						if (text.charAt( i ) == 'w')
						{
							ret += dfs( text, i, 0 );
							
						}
					}
					return ret;
				}
				
				long solve_iterative(String text)
				{
					long ret = 0;
					
					mem = new long[text.length()][welcome.length()];
					for( int i = 0; i < text.length(); ++i )
						for( int j = 0; j < welcome.length(); ++j )
							mem[i][j] = 0;
					for( int i = 0; i < text.length(); ++i )
						if (text.charAt( i ) == 'w')
							mem[i][0] = 1;
					
					for( int i = 0; i < text.length(); ++i )
					{
						for( int j = 1; j < welcome.length(); ++j )
						{
							if (text.charAt( i ) == welcome.charAt( j ))
							{
								for( int k = 0; k < i; ++k )
								{
									mem[i][j] += mem[k][j - 1] % 10000;
								}
								if (j == welcome.length() - 1)
									ret += mem[i][j] % 10000;
								ret = ret % 10000;
							}
						}
					}
					for( int i = 0; i < text.length(); ++i )
					{
						for( int j = 0; j < welcome.length(); ++j )
						{
							//System.out.print( mem[i][j] + " ");
						}
						//System.out.print( "\n");
					}
					return ret;
				}
				
				String beautify(Long num)
				{
					String ret = num.toString();
					if (ret.length() > 4)
						return ret.substring( ret.length() - 4 );
					
					while (ret.length() != 4)
						ret = '0' + ret;
					
					return ret;
				}
				
				@Override
				public void solve(InputStream inFile, PrintStream out) throws FileNotFoundException
				{
					Scanner in = new Scanner( inFile );
					
					String t;
					t = in.nextLine();
					int num_cases = Integer.parseInt( t );
					for( int case_num = 1; case_num <= num_cases; ++case_num )
					{
						System.out.println( "========== " + case_num + " ===========" );
						String line = in.nextLine();
						out.println( "Case #" + case_num + ": " + beautify( solve_iterative( line ) ) );
					}
					
				}
				
			}
			
			public static class Watersheds implements Problem
			{
				//Map<Character,List<Character>> same_basins = new HashMap<Character,List<Character>>();
				Map<Character, Character> replace = new HashMap<Character, Character>();
				
				int D[][] =
				{
						{
								0, -1
						},
						{
								-1, 0
						},
						{
								1, 0
						},
						{
								0, 1
						}
				};
				
				void DFS(int[][] board, char[][] drains, int x, int y, char cur_char)
				{
					drains[x][y] = cur_char;
					int next_move[] = next_drain( board, drains, x, y );
					//System.out.println( x + " " + y);
					//System.out.println( next_move[0] + " " + next_move[1]);
					//System.out.println( " ============ ");
					if (next_move[0] == x && next_move[1] == y)
					{
						//System.out.println( "omg");
						return;
					}
					char drain = drains[next_move[0]][next_move[1]];
					if (drain == '.')
					{
						DFS( board, drains, next_move[0], next_move[1], cur_char );
					}
					else if (drain == cur_char)
						return;
					else
					{
						/*
						if( !same_basins.containsKey(drain)) {
							same_basins.put(drain, new ArrayList<Character>());
						}
						same_basins.get(drain).add(cur_char);
						*/
						//System.out.println( "")
						//drains[x][y]=drain;
						replace.put( cur_char, drain );
					}
				}
				
				void trim_replace()
				{
					Map<Character, Character> rep_replace = new HashMap<Character, Character>();
					for( Character c : replace.keySet() )
					{
						char new_replace = c;
						while (replace.containsKey( new_replace ))
						{
							new_replace = replace.get( new_replace );
						}
						
						rep_replace.put( c, new_replace );
					}
					replace = rep_replace;
				}
				
				void sort_replace(char drains[][], int W, int H)
				{
					for( int y = 0; y < H; ++y )
					{
						for( int x = 0; x < W; ++x )
						{
							Character c = replace.get( drains[x][y] );
							c = c == null ? drains[x][y] : c;
							drains[x][y] = c;
						}
					}
					Map<Character, Character> rep_replace = new HashMap<Character, Character>();
					char largest = 'a';
					for( int y = 0; y < H; ++y )
					{
						for( int x = 0; x < W; ++x )
						{
							if (drains[x][y] > largest && !rep_replace.containsKey( drains[x][y] ))
							{
								rep_replace.put( drains[x][y], ++largest );
							}
						}
					}
					replace = rep_replace;
				}
				
				int[] next_drain(int[][] board, char[][] drains, int x, int y)
				{
					int nx = x, ny = y;
					int min_drain = board[x][y];
					for( int d = 0; d < D.length; ++d )
					{
						int tx = x + D[d][0];
						int ty = y + D[d][1];
						
						if (tx < 0 || tx >= board.length || ty < 0 || ty >= board[0].length)
							continue;
						
						if (min_drain > board[tx][ty])
						{
							min_drain = board[tx][ty];
							nx = tx;
							ny = ty;
						}
					}
					//System.out.println( x + " " + y);
					//System.out.println( nx+ " " + ny);
					int[] ret =
					{
							nx, ny
					};
					return ret;
				}
				
				@Override
				public void solve(InputStream inFile, PrintStream out) throws FileNotFoundException
				{
					Scanner in = new Scanner( inFile );
					
					int num_maps = in.nextInt();
					for( int case_num = 1; case_num <= num_maps; ++case_num )
					{
						replace.clear();
						//System.out.println( "==============");
						int H, W;
						int[][] board;
						char[][] drains;
						H = in.nextInt();
						W = in.nextInt();
						board = new int[W][H];
						drains = new char[W][H];
						for( int h = 0; h < H; ++h )
						{
							for( int w = 0; w < W; ++w )
							{
								board[w][h] = in.nextInt();
								drains[w][h] = '.';
							}
						}
						//drains[0][0] = 'a';
						char cur_drain = '`';
						for( int y = 0; y < H; ++y )
						{
							for( int x = 0; x < W; ++x )
							{
								if (drains[x][y] != '.')
									continue;
								DFS( board, drains, x, y, ++cur_drain );
								
							}
							
						}
						
						trim_replace();
						sort_replace( drains, W, H );
						
						out.println( "Case #" + case_num + ":" );
						for( int y = 0; y < H; ++y )
						{
							for( int x = 0; x < W; ++x )
							{
								Character p_char = replace.get( drains[x][y] );
								p_char = p_char == null ? drains[x][y] : p_char;
								out.print( p_char + " " );
								//System.out.println( drains[x][y] + "==>" + p_char);
							}
							out.print( "\n" );
							
						}
						
					}
					
				}
				
			}
			
			public static class AlienLanguage implements Problem
			{
				
				@Override
				public void solve(InputStream inFile, PrintStream out) throws FileNotFoundException
				{
					Scanner in = new Scanner( inFile );
					int L, D, N;
					
					L = in.nextInt();
					D = in.nextInt();
					N = in.nextInt();
					in.nextLine();
					ArrayList<String> words = new ArrayList<String>();
					
					for( int i = 0; i < D; ++i )
					{
						words.add( in.nextLine() );
						//System.out.println( "Added word " + words.get(words.size() -1 ));
					}
					for( int i = 1; i <= N; ++i )
					{
						String pattern = in.nextLine();
						pattern = pattern.replace( '(', '[' );
						pattern = pattern.replace( ')', ']' );
						//System.out.println( "case pattern = " + pattern);
						Pattern p_pattern = Pattern.compile( pattern );
						
						int num_match = 0;
						for( int j = 0; j < words.size(); ++j )
						{
							Matcher m = p_pattern.matcher( words.get( j ) );
							boolean matches = m.matches();
							num_match += matches ? 1 : 0;
							//System.out.println( words.get(j) + " matches = " + matches);
						}
						out.println( "Case #" + i + ": " + num_match );
					}
					
				}
				
			}
		}
		
		public static class Round1A_2008
		{
			public static class Numbers implements Problem
			{
				
				@Override
				public void solve(InputStream inFile, PrintStream out) throws FileNotFoundException
				{
					Scanner in = new Scanner( inFile );
					int num_cases = in.nextInt();
					BigDecimal r = new BigDecimal( 3 + Math.sqrt( 5 ), new MathContext( 1 << 30, RoundingMode.CEILING ) );
					double rd = 3 + Math.sqrt( 5 );
					for( int kase = 1; kase <= num_cases; ++kase )
					{
						int n = in.nextInt();
						
						BigDecimal ans = r.pow( n );
						double ansd = Math.pow( rd, (double) n );
						String ret = ans.toPlainString();
						//String ret = Double.toString(ansd);
						ret = ret.substring( 0, ret.indexOf( '.' ) );
						if (ret.length() == 1)
							ret = "00" + ret;
						if (ret.length() == 2)
							ret = "0" + ret;
						if (ret.length() > 3)
							ret = ret.substring( ret.length() - 3 );
						out.println( "Case #" + kase + ": " + ret );
					}
					
				}
				
			}
			
			public static class MilkShakes implements Problem
			{
				
				public static class Customer
				{
					public Set<Integer> likes = new HashSet<Integer>();
					public int malt = -1;
					
					public boolean satisfies(boolean m[])
					{
						for( int i = 1; i <= m.length; ++i )
						{
							if (likes.contains( i ) && malt == i && m[i - 1])
								return true;
							if (likes.contains( i ) && malt != i && !m[i - 1])
								return true;
						}
						return false;
					}
					
					public boolean satisfies(int milkshake, boolean malted)
					{
						if (!likes.contains( milkshake ))
							return false;
						
						if (malted)
						{
							if (malt == milkshake)
								return true;
							return false;
						}
						return true;
					}
					
					public String toString()
					{
						String ret = "";
						ret = "customer likes: ";
						for( Integer i : likes )
						{
							ret += i + " ";
						}
						ret += " malt: " + malt;
						return ret;
					}
				}
				
				String printBoolean(boolean[] arr)
				{
					String ret = "";
					for( int i = 0; i < arr.length; ++i )
					{
						ret += arr[i] ? "1 " : "0 ";
					}
					return ret;
				}
				
				boolean[] solve(ArrayList<Customer> customers, int num_milkshakes)
				{
					int n = (1 << num_milkshakes) - 1;
					//System.out.println( n);
					boolean ret[] = new boolean[num_milkshakes];
					for( int i = 0; i <= n; ++i )
					{
						for( int k = 0; k < num_milkshakes; ++k )
						{
							ret[k] = (i & (1 << k)) != 0;
						}
						//System.out.println( i );
						//System.out.println( printBoolean(ret) );
						boolean good = true;
						for( Customer cust : customers )
						{
							boolean t = cust.satisfies( ret );
							//System.out.println( cust );
							//System.out.println( t );
							if (!t)
							{
								good = false;
								break;
							}
						}
						if (good)
							return ret;
					}
					return null;
				}
				
				boolean[] solve2(ArrayList<Customer> customers, int num_milkshakes)
				{
					/*
					HashSet<Integer> unmalted[] = new HashSet[num_milkshakes];
					HashSet<Integer> malted[] = new HashSet[num_milkshakes];
					
					for( int i = 0; i < num_milkshakes; ++i )
					{
						unmalted[i] =  new HashSet<Integer>();
						malted[i] = new HashSet<Integer>();
					}
					
					for( int i = 0; i < customers.size(); ++i )
					{
						for( int k = 0; k < num_milkshakes; ++k )
						{
							if( customers.get(i).satisfies(k, false) ) unmalted[k].add(i);
							if( customers.get(i).satisfies(k, true )) malted[k].add(i);
						}
					}
					*/

					boolean[] ret = new boolean[num_milkshakes];
					for( int i = 0; i < num_milkshakes; ++i )
						ret[i] = false;
					while (true)
					{
						boolean ok = true;
						for( int i = 0; i < customers.size(); ++i )
						{
							boolean s = customers.get( i ).satisfies( ret );
							if (!s)
							{
								if (customers.get( i ).malt == -1)
									return null;
								ret[customers.get( i ).malt - 1] = true;
								customers.remove( i );
								ok = false;
								break;
								
							}
						}
						if (ok)
							break;
					}
					
					return ret;
					
				}
				
				@Override
				public void solve(InputStream inFile, PrintStream out) throws FileNotFoundException
				{
					Scanner in = new Scanner( inFile );
					
					int num_cases = in.nextInt();
					for( int kase = 1; kase <= num_cases; ++kase )
					{
						int N = in.nextInt();
						int M = in.nextInt();
						ArrayList<Customer> customers = new ArrayList<Customer>();
						for( int i = 0; i < M; ++i )
						{
							int T = in.nextInt();
							Customer cust = new Customer();
							for( int k = 0; k < T; ++k )
							{
								int m = in.nextInt();
								int mm = in.nextInt();
								cust.likes.add( m );
								if (mm == 1)
								{
									cust.malt = m;
								}
								else
								{
									if (cust.malt == m)
										cust.malt = -1;
								}
							}
							customers.add( cust );
						}
						boolean solution[] = solve2( customers, N );
						out.println( "Case #" + kase + ": " + (solution == null ? "IMPOSSIBLE" : printBoolean( solution )) );
						
					}
					
				}
				
			}
			
			public static class MinimumScalarProduct implements Problem

			{
				
				@Override
				public void solve(InputStream in_file, PrintStream out) throws FileNotFoundException
				{
					Scanner in = new Scanner( in_file );
					int num_cases = in.nextInt();
					for( int i = 0; i < num_cases; ++i )
					{
						int n = in.nextInt();
						ArrayList<Long> x = new ArrayList<Long>( n );
						ArrayList<Long> y = new ArrayList<Long>( n );
						for( int k = 0; k < n; ++k )
						{
							x.add( in.nextLong() );
						}
						for( int k = 0; k < n; ++k )
						{
							y.add( in.nextLong() );
						}
						
						Collections.sort( x );
						Collections.sort( y );
						Collections.reverse( y );
						long ret = 0;
						for( int k = 0; k < n; ++k )
						{
							ret += x.get( k ) * y.get( k );
						}
						out.println( "Case #" + (i + 1) + ": " + ret );
					}
				}
			}
		}
		
		public static class Round1A_2009
		{
			public static class MultiBaseHappiness implements Problem
			{
				
				static HashMap<Long, String>[] conv_mem = new HashMap[11];
				static
				{
					for( int i = 2; i <= 10; ++i )
					{
						conv_mem[i] = new HashMap<Long, String>();
					}
				}
				
				String convert(long i, int base)
				{
					if (conv_mem[base].containsKey( i ))
						return conv_mem[base].get( i );
					
					String ret = "";
					
					while (i > 0)
					{
						ret = i % base + ret;
						i /= base;
					}
					conv_mem[base].put( i, ret );
					return ret;
				}
				
				int convert(String numb, int base)
				{
					int ret = 0;
					int c = 0;
					for( int i = numb.length() - 1; i >= 0; --i )
					{
						ret += Math.pow( base, c ) * (numb.charAt( i ) - 48);
						++c;
					}
					return ret;
				}
				
				String next_step(String str, int base)
				{
					long sum = 0;
					for( int i = 0; i < str.length(); ++i )
					{
						char[] t =
						{
							str.charAt( i )
						};
						int k = convert( new String( t ), base );
						sum += k * k;
					}
					return convert( sum, base );
				}
				
				//String step
				
				static HashMap<String, Boolean> happy_mem[] = new HashMap[11];
				
				static
				{
					for( int i = 2; i <= 10; ++i )
					{
						happy_mem[i] = new HashMap<String, Boolean>();
					}
				}
				
				boolean isHappy(String t, int base, Set<String> already)
				{
					if (t.equals( "1" ))
						return true;
					if (already.contains( t ))
						return false;
					if (happy_mem[base].containsKey( t ))
						return happy_mem[base].get( t );
					
					already.add( t );
					
					String next = next_step( t, base );
					
					boolean ret = isHappy( next, base, already );
					happy_mem[base].put( t, ret );
					return ret;
					
				}
				
				boolean isHappy(int i, int base)
				{
					
					String t = convert( i, base );
					HashSet<String> set = new HashSet<String>();
					Boolean happy = null;
					while (!t.equals( "1" ) && !set.contains( t ))
					{
						set.add( t );
						t = next_step( t, base );
						if (happy_mem[base].containsKey( t ))
						{
							happy = new Boolean( happy_mem[base].get( t ) );
							break;
						}
					}
					happy = happy == null ? t.equals( "1" ) : happy;
					
					for( String k : set )
					{
						happy_mem[base].put( k, happy );
					}
					
					return happy;
					
					//return isHappy( convert( i, base ), base, new HashSet<String>());
				}
				
				static int lim = 1 * (int) 1e6;
				static boolean[][] happiness = new boolean[lim][11];
				
				void precomptue()
				{
					for( int base = 2; base <= 10; ++base )
					{
						for( int i = 2; i < lim; ++i )
						{
							happiness[i][base] = isHappy( i, base );
						}
					}
					System.out.println( "done precomputing" );
				}
				
				int findHappy(ArrayList<Integer> bases)
				{
					int ret = 0;
					
					for( int i = 2; i < lim; ++i )
					{
						boolean isgood = true;
						for( Integer k : bases )
						{
							if (!happiness[i][k])
							{
								isgood = false;
								break;
							}
						}
						if (isgood)
							return i;
					}
					
					return ret;
				}
				
				@Override
				public void solve(InputStream inFile, PrintStream out) throws FileNotFoundException
				{
					precomptue();
					Scanner in = new Scanner( inFile );
					int T = in.nextInt();
					in.nextLine();
					for( int case_num = 1; case_num <= T; ++case_num )
					{
						String line = in.nextLine();
						ArrayList<Integer> bases = new ArrayList<Integer>();
						StringTokenizer tokenizer = new StringTokenizer( line, " " );
						while (tokenizer.hasMoreTokens())
						{
							bases.add( Integer.parseInt( tokenizer.nextToken() ) );
						}
						out.println( "Case #" + case_num + ": " + findHappy( bases ) );
						System.out.println( convert( 82, 10 ) );
						//    System.out.println( convert( "82", 10 ));
						//System.out.println( isHappy( 51, 2));
						//	System.out.println( next_step( "82",10));
					}
					
				}
				
			}
			
			public static class CrossingTheRoad implements Problem
			{
				
				int wait(int S[][], int W[][], int T[][], int i, int j, int t, boolean north_south)
				{
					int p = S[i][j] + W[i][j];
					int k = T[i][j] % p;
					int c = Math.abs( (t - k) % p );
					//c= p % t + T[i][j] %p;
					
					System.out.println( c );
					//int k = t/T[i][j];
					return t;
				}
				
				@Override
				public void solve(InputStream inFile, PrintStream out) throws FileNotFoundException
				{
					Scanner in = new Scanner( inFile );
					int C = in.nextInt();
					for( int case_num = 1; case_num <= C; ++case_num )
					{
						int N, M;
						N = in.nextInt();
						M = in.nextInt();
						
						int S[][] = new int[N][M];
						int W[][] = new int[N][M];
						int T[][] = new int[N][M];
						for( int i = 0; i < N; ++i )
						{
							for( int j = 0; j < M; ++j )
							{
								S[i][j] = in.nextInt();
								W[i][j] = in.nextInt();
								T[i][j] = in.nextInt();
							}
						}
						wait( S, W, T, 0, 0, 4, true );
						
					}
				}
				
			}
		}
		
		public static class Round1B_2009
		{
			public static class DecisionTree implements Problem
			{
				
				public static class animal
				{
					Set<String> attr = new HashSet<String>();
					double prob = 1;
					String name;
					
					void compute(StringTokenizer t)
					{
						//t.nextToken();
						String p = t.nextToken();
						if (p.equals( "(" ))
							p = t.nextToken();
						System.out.println( name + " " + p );
						prob *= Double.parseDouble( p );
						p = t.nextToken();
						
						System.out.println( name + " " + p );
						
						if (p.equals( ")" ))
						{
							return;
						}
						if (attr.contains( p ))
						{
							System.out.println( name + " is " + p );
							compute( t );
						}
						else
						{
							System.out.println( name + " is not " + p );
							int z = 0;
							boolean ok_to_break = false;
							while (true)
							{
								if (ok_to_break && z == 0)
									break;
								p = t.nextToken();
								if (p.equals( "(" ))
								{
									++z;
									ok_to_break = true;
								}
								if (p.equals( ")" ))
								{
									--z;
									
								}
								System.out.println( "skipping " + p );
							}
							compute( t );
						}
						
					}
				}
				
				public void solve(InputStream inFile, PrintStream out) throws FileNotFoundException
				{
					Scanner in = new Scanner( inFile );
					
					int N = in.nextInt();
					for( int case_num = 1; case_num <= N; ++case_num )
					{
						ArrayList<animal> animals = new ArrayList<animal>();
						
						int L = in.nextInt();
						in.nextLine();
						String tree = "";
						for( int i = 0; i < L; ++i )
							tree += in.nextLine();
						tree = tree.replace( "(", " ( " );
						tree = tree.replace( ")", " )  " );
						System.out.println( tree );
						int A = in.nextInt();
						in.nextLine();
						for( int i = 0; i < A; ++i )
						{
							String t = in.nextLine();
							//System.out.println(t);
							StringTokenizer tokenizer = new StringTokenizer( t, " " );
							animal new_animal = new animal();
							new_animal.name = tokenizer.nextToken();
							tokenizer.nextToken();
							
							while (tokenizer.hasMoreTokens())
								new_animal.attr.add( tokenizer.nextToken() );
							animals.add( new_animal );
						}
						
						out.println( "Case #" + case_num + ": " );
						for( animal an : animals )
						{
							//System.out.println( an.attr);
							an.compute( new StringTokenizer( tree, " " ) );
							out.println( an.prob );
						}
					}
				}
			}
			
			public static class TheNextNumber implements facebook_problem
			{
				
				public static String conv(int[] t)
				{
					String ret = "";
					for( int i = 0; i < t.length; ++i )
					{
						ret += Integer.toString( t[i] );
					}
					return ret;
				}
				
				@Override
				public void solve(InputStream inFile, PrintStream out) throws FileNotFoundException
				{
					Scanner in = new Scanner( inFile );
					int T = in.nextInt();
					in.nextLine();
					for( int case_num = 1; case_num <= T; ++case_num )
					{
						String N = in.nextLine();
						int[] c_N = new int[N.length()];
						for( int i = 0; i < N.length(); ++i )
							c_N[i] = N.charAt( i ) - 48;
						boolean p = Util.Perm.nextPerm( c_N );
						if (!p)
						{
							
						}
						out.println( "Case #" + case_num + ": " + conv( c_N ) );
					}
				}
			}
		}
		
		public static class Round1C_2008
		{
			public static class IncreasingSpeedLimits implements Problem
			{
				
				@Override
				public void solve(InputStream inFile, PrintStream out) throws FileNotFoundException
				{
					Scanner in = new Scanner( inFile );
					
					int N = in.nextInt();
					for( int case_num = 1; case_num <= N; ++case_num )
					{
						int n, m, X, Y, Z;
						n = in.nextInt();
						m = in.nextInt();
						X = in.nextInt();
						Y = in.nextInt();
						Z = in.nextInt();
						int A[] = new int[m];
						for( int i = 0; i < m; ++i )
							A[i] = in.nextInt();
						int c = 0;
						long seq[] = new long[n];
						for( int i = 0; i < n; ++i )
						{
							seq[c++] = A[i % m];
							A[i % m] = (X * A[i % m] + Y * (i + 1)) % Z;
						}
					}
					
				}
				
			}
			
			public static class UglyNumbers implements Problem
			{
				
				@Override
				public void solve(InputStream inFile, PrintStream out) throws FileNotFoundException
				{
					Scanner in = new Scanner( inFile );
					int N = in.nextInt();
					in.nextLine();
					for( int case_num = 1; case_num <= N; ++case_num )
					{
						String num = in.nextLine();
						System.out.println( num );
					}
				}
				
			}
			
			public static class TextMessagingOutrage implements Problem
			{
				
				@Override
				public void solve(InputStream inFile, PrintStream out) throws FileNotFoundException
				{
					Scanner in = new Scanner( inFile );
					int N = in.nextInt();
					for( int case_num = 1; case_num <= N; ++case_num )
					{
						int P = in.nextInt();
						int K = in.nextInt();
						int L = in.nextInt();
						long[] freq = new long[L];
						for( int i = 0; i < L; ++i )
							freq[i] = in.nextLong();
						long min_presses = 0;
						Arrays.sort( freq );
						int mult = 1;
						int k = 0;
						for( int i = freq.length - 1; i >= 0; --i )
						{
							min_presses += freq[i] * mult;
							
							if (++k % K == 0)
								mult++;
						}
						out.println( "Case #" + case_num + ": " + min_presses );
					}
					
				}
				
			}
		}
		
		public static class Round1C_2009
		{
			public static class BribeThePrisoners implements Problem
			{
				
				int solve(int[] release, int[][] dp, int a, int b)
				{
					if (b >= dp[0].length || a >= dp.length || a <= 0 || b <= 0)
						return 0;
					if (dp[a][b] != -1)
						return dp[a][b];
					int ret = 0;
					for( int i = release.length - 1; i >= 0; --i )
					{
						if (release[i] >= a && release[i] <= b)
						{
							int t = (b - a) + solve( release, dp, a, release[i] - 1 ) + solve( release, dp, release[i] + 1, b );
							if (ret == 0 || t < ret)
								ret = t;
						}
					}
					//System.out.println( ret );
					dp[a][b] = ret;
					return ret;
				}
				
				@Override
				public void solve(InputStream inFile, PrintStream out) throws Exception
				{
					
					Scanner in = new Scanner( inFile );
					//System.out.println( in);
					//in.next();
					int N = in.nextInt();
					for( int case_num = 1; case_num <= N; ++case_num )
					{
						System.out.println( "==== " + case_num + " ===" );
						int P, Q;
						P = in.nextInt();
						Q = in.nextInt();
						System.out.println( P + " " + Q );
						int[] release = new int[Q];
						for( int i = 0; i < Q; ++i )
							release[i] = in.nextInt();
						int[][] dp = new int[P + 1][P + 1];
						for( int i = 0; i < P + 1; ++i )
							for( int j = 0; j < P + 1; ++j )
								dp[i][j] = -1;
						//for( int i = 0; i < Q; ++i) System.out.println( release[i]);
						int sol = P > 1 ? solve( release, dp, 1, P ) : P - Q;
						
						out.println( "Case #" + case_num + ": " + sol );
						
					}
					
				}
				
			}
		}
		
		public static class Round2_2008
		{
			public static class CheatingABooleanTree implements Problem
			{
				
				public static class node
				{
					int op;
					boolean change;
					node left = null, right = null;
					node parent = null;
					boolean leaf;
					int leaf_val;
					
					int min_flips[] = new int[2];
					
					public node()
					{
						min_flips[0] = min_flips[1] = -1;
					}
					
					public void addChild(node n)
					{
						if (left == null)
							left = n;
						else
							right = n;
						n.parent = this;
					}
					
					public int comp()
					{
						if (leaf)
							return leaf_val;
						return op == 1 ? left.comp() & right.comp() : left.comp() | right.comp();
					}
					
					public int min_flips(int desired)
					{
						if (comp() == desired)
							return 0;
						if (leaf && desired != leaf_val)
							return 1;
						else if (leaf)
							return 0;
						
						int ret = 0;
						int left_min = left.min_flips( desired );
						int right_min = right.min_flips( desired );
						int n_left_min = left.min_flips( desired == 0 ? 1 : 0 );
						int n_right_min = left.min_flips( desired == 0 ? 1 : 0 );
						
						if (desired == 0 && op == 0)
						{
							if (!change)
							{
								ret = left_min + right_min;
							}
							else
							{
								ret = Math.min( 1 + left_min, 1 + right_min );
							}
						}
						if (desired == 0 && op == 1)
						{
							ret = Math.min( left_min, right_min );
						}
						if (desired == 1 && op == 1)
						{
							if (!change)
							{
								ret = left_min + right_min;
							}
							else
							{
								ret = Math.min( 1 + left_min, 1 + right_min );
							}
						}
						if (desired == 1 && op == 0)
						{
							ret = Math.min( left_min, right_min );
						}
						
						//	if( ret == 0) return Integer.MAX_VALUE;
						return ret;
					}
					
				}
				
				@Override
				public void solve(InputStream inFile, PrintStream out) throws FileNotFoundException
				{
					Scanner in = new Scanner( inFile );
					int N = in.nextInt();
					for( int case_num = 1; case_num <= N; ++case_num )
					{
						System.out.println( "Case # " + case_num );
						int M, V;
						M = in.nextInt();
						V = in.nextInt();
						node[] nodes = new node[M];
						node V_NODE;
						node cur = null;
						int i;
						for( i = 0; i < (M - 1) / 2; ++i )
						{
							nodes[i] = new node();
							
							nodes[i].leaf = false;
							
							int G, C;
							G = in.nextInt();
							C = in.nextInt();
							
							nodes[i].change = C == 1 ? true : false;
							nodes[i].op = G;
							
							if (i > 0)
							{
								int parent = (i - 1) / 2;
								nodes[parent].addChild( nodes[i] );
							}
						}
						for( ; i < M; ++i )
						{
							nodes[i] = new node();
							nodes[i].leaf = true;
							nodes[i].leaf_val = in.nextInt();
							int parent = (i - 1) / 2;
							nodes[parent].addChild( nodes[i] );
						}
						
						int ret = nodes[0].min_flips( V );
						out.println( "Case #" + case_num + ": " + (ret == Integer.MAX_VALUE ? "IMPOSSIBLE" : ((ret - 1) % Integer.MAX_VALUE)) );
					}
					
				}
				
			}
		}
		
		public static class Round2_2009
		{
			public static class A implements Problem
			{
				int zero(String a)
				{
					int ret = 0;
					for( int i = a.length() - 1; i >= 0; --i )
					{
						if (a.charAt( i ) != '0')
							break;
						ret++;
					}
					return ret;
				}
				
				void swap(ArrayList<String> matrix, int a, int b)
				{
					String t = matrix.get( a );
					matrix.set( a, matrix.get( b ) );
					matrix.set( b, t );
				}
				
				@Override
				public void solve(InputStream inFile, PrintStream out) throws Exception
				{
					Scanner in = new Scanner( inFile );
					int T = in.nextInt();
					for( int case_num = 1; case_num <= T; ++case_num )
					{
						//	System.out.println( "==========");
						
						int N = in.nextInt();
						in.nextLine();
						int k = 0;
						int num = 0;
						ArrayList<String> matrix = new ArrayList<String>();
						for( int i = 0; i < N; ++i )
						{
							String line = in.nextLine();
							matrix.add( line );
						}
						while (k < N)
						{
							int z = k;
							for( int i = k; i < N; ++i )
							{
								int p = zero( matrix.get( i ) );
								if (p >= N - (k + 1))
								{
									z = i;
									break;
								}
							}
							for( int j = z; j > k; --j )
							{
								swap( matrix, j, j - 1 );
							}
							num += z - k;
							//System.out.println( num );
							++k;
						}
						out.println( "Case #" + case_num + ": " + num );
					}
					
				}
			}
			
			public static class B implements Problem
			{
				public static int num_nodes = 1;
				public static Map<Integer, node> num2node = new HashMap<Integer, node>();
				
				public static class node
				{
					int n;
					boolean goal = false;
					ArrayList<node> can_get_to = new ArrayList<node>();
				}
				
				int D[][] =
				{
						{
								1, 0
						},
						{
								-1, 0
						}
				};
				
				int DIG[][] =
				{
						{
								1, 1
						},
						{
								-1, 1
						}
				};
				
				int fall(char[][] cave, int x, int y)
				{
					int ret = 0;
					while (y < cave.length && cave[y][x] == '.')
					{
						++ret;
						++y;
					}
					return ret;
				}
				
				void build_graph(char[][] cave, int[][] mark, int F, node curr_node, int x, int y, boolean dug)
				{
					
					if (y >= cave.length || y < 0 || x >= cave[0].length || x < 0)
						return;
					if (mark[y][x] > 0)
						return;
					if (cave[y][x] == '#' && !dug)
						return;
					mark[y][x] = curr_node.n;
					if (cave[y][x] == '.' || dug)
					{
						if (y == cave.length - 1)
							curr_node.goal = true;
						for( int i = 0; i < D.length; ++i )
						{
							build_graph( cave, mark, F, curr_node, x + D[i][0], y + D[i][1], false );
						}
						int f = fall( cave, x, y );
						if (f <= F)
							build_graph( cave, mark, F, curr_node, x, y + 1, false );
						
						// try to dig left and right;
						for( int i = 0; i < DIG.length; ++i )
						{
							int x1 = x + DIG[i][0];
							int y1 = y + DIG[i][1];
							if (x1 < cave[0].length && x1 >= 0 && y1 >= 0 && y1 < cave.length)
							{
								if (y1 < cave.length - 1)
								{
									if (cave[y][x1] == '.' && cave[y1][x1] == '#')
									{
										//cave[y1][x1]='.';
										int fall = 1 + fall( cave, x1, y1 + 1 );
										if (fall <= F)
										{
											
											int num = mark[y1 + 1][x1];
											if (num > 0)
											{
												curr_node.can_get_to.add( num2node.get( num ) );
											}
											else
											{
												node new_node = new node();
												new_node.n = ++num_nodes;
												curr_node.can_get_to.add( new_node );
												num2node.put( new_node.n, new_node );
												build_graph( cave, mark, F, new_node, x1, y1, true );
											}
										}
									}
								}
							}
						}
					}
					
				}
				
				int solve(node n)
				{
					if (n.goal)
						return 0;
					int ret = 1;
					int m = Integer.MAX_VALUE;
					for( node child : n.can_get_to )
					{
						m = Math.min( m, solve( child ) );
					}
					
					return ret + m;
				}
				
				@Override
				public void solve(InputStream inFile, PrintStream out) throws Exception
				{
					Scanner in = new Scanner( inFile );
					int N = in.nextInt();
					for( int case_num = 1; case_num <= N; ++case_num )
					{
						int R, C, F;
						R = in.nextInt();
						C = in.nextInt();
						F = in.nextInt();
						in.nextLine();
						char[][] cave = new char[R][];
						for( int i = 0; i < R; ++i )
							cave[i] = in.nextLine().toCharArray();
						int[][] mark = new int[R][C];
						for( int i = 0; i < R; ++i )
							for( int j = 0; j < C; ++j )
								mark[i][j] = 0;
						node root = new node();
						root.n = num_nodes;
						build_graph( cave, mark, F, root, 0, 0, false );
						out.println( "Case #" + case_num + ": " + solve( root ) );
					}
					
				}
				
			}
			
			public static class C implements Problem
			{
				
				int solve(Map<Integer, Set<Integer>> intersections, Set<Integer> done, int k)
				{
					if (done.contains( k ))
						return 0;
					done.add( k );
					if (!intersections.containsKey( k ))
						return 0;
					int ret = 1;
					if (intersections.containsKey( k ))
					{
						for( Integer z : intersections.get( k ) )
						{
							ret += solve( intersections, done, z );
						}
					}
					return ret;
				}
				
				@Override
				public void solve(InputStream inFile, PrintStream out) throws Exception
				{
					Scanner in = new Scanner( inFile );
					int T = in.nextInt();
					for( int case_num = 1; case_num <= T; ++case_num )
					{
						int n, k;
						n = in.nextInt();
						k = in.nextInt();
						double stocks[][] = new double[n][k];
						for( int i = 0; i < n; ++i )
						{
							for( int j = 0; j < k; ++j )
							{
								stocks[i][j] = in.nextDouble();
							}
						}
						Map<Integer, Set<Integer>> intersections = new HashMap<Integer, Set<Integer>>();
						for( int i = 0; i < n; ++i )
						{
							for( int j = 0; j < n; ++j )
							{
								if (i == j)
									continue;
								for( int z = 0; z < k - 1; ++z )
								{
									if (Line2D.linesIntersect( z, stocks[i][z], z + 1, stocks[i][z + 1], z, stocks[j][z], z + 1, stocks[j][z + 1] ))
									{
										if (!intersections.containsKey( i ))
											intersections.put( i, new HashSet<Integer>() );
										intersections.get( i ).add( j );
									}
									
								}
							}
						}
						Map<Integer, List<Integer>> together = new HashMap<Integer, List<Integer>>();
						for( Integer z : intersections.keySet() )
						{
							for( Integer zk : together.keySet() )
							{
								for( Integer lol : together.get( zk ) )
								{
									if (lol == z)
										continue;
								}
							}
							together.put( z, new ArrayList<Integer>() );
							for( int i = 0; i < n; ++i )
							{
								if (!intersections.get( z ).contains( i ))
								{
									together.get( z ).add( i );
								}
							}
						}
						int sol = Integer.MAX_VALUE;
						out.println( "Case #" + case_num + ": " + solve( intersections, new HashSet<Integer>(), 0 ) );
					}
					
				}
				
			}
			
			public static class D implements Problem
			{
				
				public double dist(int x, int y, int x1, int y2)
				{
					return Math.sqrt( (Math.pow( (x1 - x), 2 ) + Math.pow( y2 - y, 2 )) );
				}
				
				@Override
				public void solve(InputStream inFile, PrintStream out) throws Exception
				{
					Scanner in = new Scanner( inFile );
					int C = in.nextInt();
					for( int case_num = 1; case_num <= C; ++case_num )
					{
						int N = in.nextInt();
						int[] x = new int[N];
						int[] y = new int[N];
						int[] r = new int[N];
						for( int i = 0; i < N; ++i )
						{
							x[i] = in.nextInt();
							y[i] = in.nextInt();
							r[i] = in.nextInt();
						}
						double sol = 0;
						if (N == 1)
							sol = (double) r[0];
						if (N == 2)
						{
							sol = (double) Math.max( r[0], r[1] );
						}
						if (N == 3)
						{
							double rad1 = dist( x[0], y[0], x[1], y[1] ) + r[0] + r[1];
							double rad2 = dist( x[1], y[1], x[2], y[2] ) + r[1] + r[2];
							double rad3 = dist( x[0], y[0], x[2], y[2] ) + r[0] + r[2];
							sol = Math.min( rad1, Math.min( rad2, rad3 ) ) / 2;
							
						}
						else
						{
							
						}
						
						out.println( "Case #" + case_num + ": " + sol );
						
					}
					
				}
				
			}
		}
		
	}
	
	public static class ACM_Problems
	{
		public static class Codeforces
		{
			public static class Round9
			{
				public static class A implements acm_problem
				{

					
					public void solve(InputStream in, PrintStream out) throws Exception
					{
						Scanner scanner = new Scanner(in);
						Integer Y,W;
						Y = scanner.nextInt();
						W = scanner.nextInt();
						Integer M = Math.max( Y, W );
						if( M == 1 )
						{
							out.println( "1/1");
						}
						if( M == 2 )
						{
							out.println( "5/6" );
						}
						if( M == 3 )
						{
							out.println( "2/3");
						}
						if( M == 4 )
						{
							out.println( "1/2");
						}
						if( M == 5 )
						{
							out.println( "1/3");
						}
						if( M == 6)
						{
							out.println( "1/6");
						}
						
					}
					
				}
			}
		}
	}
	
	
	public static void solveProblem(Problem prob, String input_file, String output_file) throws Exception
	{
		
		PrintStream out;
		InputStream in;
		if (prob instanceof acm_problem)
		{
			in = System.in;
			out = System.out;
		}
		else
		{
			in = new FileInputStream( input_file );
			if (!(prob instanceof facebook_problem))
			{
				FileOutputStream ofs = new FileOutputStream( output_file );
				out = new PrintStream( ofs );
			}
			else
				out = System.out;
		}
		
		prob.solve( in, out );
	}
	
	/**
	 * @param args
	 * @throws IOException
	 */
	public static void main(String[] args)
	{
		try
		{
			solveProblem( new ACM_Problems.Codeforces.Round9.A(), "A-small-practice.in", "output.txt" );
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
	}
}
