Decimal numbers are a common notation system currently in use and use ten symbols 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9 to represent all numbers.

Binary numbers are a popular notation in the computer world and use two symbols, 0 and 1, to represent all numbers.

Only the four numbers 0, 1, 2, and 3 are used in quaternary numbers. In quaternary numbers, when the number is incremented from 0, it will be carried to the next digit when it reaches 4. Therefore, the decimal number 4 is carried to the expression "10".

Decimal | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ...
--- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |- ---
Binary | 0 | 1 | 10 | 11 | 100 | 101 | 110 | 111 | 1000 | 101 | 1010 | ...
Quadrant | 0 | 1 | 2 | 3 | 10 | 11 | 12 | 13 | 20 | 21 | 22 | ...



In Hawaii, fish and taro were counted between fingers in the old days, so it seems that they used quaternary numbers instead of decimal numbers.

Create a program that converts the integer n input in decimal to decimal and outputs it.



Input

A sequence of multiple datasets is given as input. The end of the input is indicated by a single line of -1. One integer n (0 ≤ n ≤ 1000000) is given on one row for each dataset.

The number of datasets does not exceed 2000.

Output

The result of conversion to quaternary number for each input data set is output on one line.

Example

Input

7
4
0
12
10
10000
-1


Output

13
10
0
30
22
2130100

import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
	static int[][] list;
	public static void main(String[] args) {
		
		FastScanner sc = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);

		while(true) {
			int n = sc.nextInt();
			if(n == -1) break;
			out.println(Integer.toString(n, 4));
		}
		out.flush();
	}
	static void solv(int a, int b, boolean[] c) {
		list[a][b]++;
		if(a == 9) return;
		if(b > 1000) return;
		
		for(int i = 0; i < 101; i++) {
			if(a == 8) {
				if(!c[i]) {
					list[a+1][b+i]++;
				}
			}
			
			else if(!c[i]) {
				c[i] = true;
				solv(a+1,b+i,c);
				c[i] = false;
			}
		}
	}
}
//------------------------------//
//-----------//
class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
    public boolean hasNext() { skipUnprintable(); return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    
    public int nextInt() {
    	return (int)nextLong();
    }
    

}