In order to protect the southern border of Bytelandian Empire against intrusions by various nomadic groups, the Emperor of Byteland has decided to build a wall along the southern border. The best architect Johny is recruited for the task.

In order to protect the southern border of Bytelandian Empire against intrusions by various nomadic groups, the Emperor of Byteland has decided to build a wall along the southern border. The best architect Johny is recruited for the task.

Given a complete binary tree with the height of H, we index the nodes respectively top-down and left-right from 1. The i-th node stores a positive integer V_i. Define P_i as follows: P_i=V_i if the i-th node is a leaf, otherwise P_i=max(V_i*P_L, V_i*P_R), where L and R are the indices of the left and right children of i, respectively. Your task is to caculate the value of P₁.

Input

There are several test cases (fifteen at most), each formed as follows:

Many internet protocols these days include the option of associating a media type with the content being sent. The type is usually inferred from the file extension. You are to write a program that facilitates the lookup of media types for a number of files.

Chef has been exploring prime numbers lately, and has recently made a conjecture resembling one of Goldbach's conjectures. Chef's conjecture is that any odd number greater than 61 can be expressed as the sum of a prime, a square of a prime, and a cube of a prime. He wants you to help verify his conjecture for small numbers.

Note: negative numbers are never considered to be prime, nor are 0 and 1.