/* package whatever; // don't place package name! */
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int n;
		int result;
		for (n=0;n<=16;n++) {
			result = nextPower2(n);
			System.out.println("Next power of " + n + " is " + result);
		}
	}
 
	static int nextPower(int n) {
		int result;
		result = nextPower1(n);
		if (n<=1 || result ==n)
			return result;
		else
			return result * 2;
	}
 
	 static int nextPower2( int n ) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    if (n == 3) return 4;
    return nextPower((n >> 1) | (n & 1)) << 1;
}
 
	static int nextPower1(int n) {
	    if(n == 0) {
	        return 1;
	    } else if(n == 1) {
	        return 1;
	    } else {
	        int lastBit = n & 1;
	        int secondLastBit = (n >> 1) & 1;
	        int restOfTheBits = (n >> 2);
 
	        int result = nextPower1(restOfTheBits << 1 | secondLastBit ^ lastBit);
	        return result << 1;
	    }
	}
}

LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCWludCBuOwoJCWludCByZXN1bHQ7CgkJZm9yIChuPTA7bjw9MTY7bisrKSB7CgkJCXJlc3VsdCA9IG5leHRQb3dlcjIobik7CgkJCVN5c3RlbS5vdXQucHJpbnRsbigiTmV4dCBwb3dlciBvZiAiICsgbiArICIgaXMgIiArIHJlc3VsdCk7CgkJfQoJfQoJCglzdGF0aWMgaW50IG5leHRQb3dlcihpbnQgbikgewoJCWludCByZXN1bHQ7CgkJcmVzdWx0ID0gbmV4dFBvd2VyMShuKTsKCQlpZiAobjw9MSB8fCByZXN1bHQgPT1uKQoJCQlyZXR1cm4gcmVzdWx0OwoJCWVsc2UKCQkJcmV0dXJuIHJlc3VsdCAqIDI7Cgl9CgkKCSBzdGF0aWMgaW50IG5leHRQb3dlcjIoIGludCBuICkgewogICAgaWYgKG4gPT0gMSkgcmV0dXJuIDE7CiAgICBpZiAobiA9PSAyKSByZXR1cm4gMjsKICAgIGlmIChuID09IDMpIHJldHVybiA0OwogICAgcmV0dXJuIG5leHRQb3dlcigobiA+PiAxKSB8IChuICYgMSkpIDw8IDE7Cn0KCQoJc3RhdGljIGludCBuZXh0UG93ZXIxKGludCBuKSB7CgkgICAgaWYobiA9PSAwKSB7CgkgICAgICAgIHJldHVybiAxOwoJICAgIH0gZWxzZSBpZihuID09IDEpIHsKCSAgICAgICAgcmV0dXJuIDE7CgkgICAgfSBlbHNlIHsKCSAgICAgICAgaW50IGxhc3RCaXQgPSBuICYgMTsKCSAgICAgICAgaW50IHNlY29uZExhc3RCaXQgPSAobiA+PiAxKSAmIDE7CgkgICAgICAgIGludCByZXN0T2ZUaGVCaXRzID0gKG4gPj4gMik7CgkKCSAgICAgICAgaW50IHJlc3VsdCA9IG5leHRQb3dlcjEocmVzdE9mVGhlQml0cyA8PCAxIHwgc2Vjb25kTGFzdEJpdCBeIGxhc3RCaXQpOwoJICAgICAgICByZXR1cm4gcmVzdWx0IDw8IDE7CgkgICAgfQoJfQp9