#include <iostream>
 
int jacobi(int q, int p)
{
    int s = 0, u = q, v = p;
    int r, k, t;
    do{
        // Вычисляем r - наименьший положительный остаток при делении u на v
        r = u % v;
        // Вычисляем целое k >= 0 и нечетное t: r = t * 2^k
        k = t = 0;
        while(r % 2 == 0)
        {
            k++;        // Показатель степени двойки в числе r
            r >>= 1;    // Делим r на 2
        }
        t = r;          // В t находится результат деления r на 2^k
        s = (s + k * (v*v - 1)/8 + (t - 1)*(v - 1)/4) % 2;
        if(t == 1)
            return (s) ? -1 : 1;
        // Новая итерация
        u = v;
        v = t;
    }while(t >= 3);
}
 
int main() {
	std::cout << jacobi(6, 11) << std::endl; 		// -1
	std::cout << jacobi(226, 135) << std::endl;		// 1
	std::cout << jacobi(26, 35) << std::endl;		// -1
	std::cout << jacobi(888, 1999) << std::endl;	// -1
    std::cout << jacobi(893, 997) << std::endl;
    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgoKaW50IGphY29iaShpbnQgcSwgaW50IHApCnsKICAgIGludCBzID0gMCwgdSA9IHEsIHYgPSBwOwogICAgaW50IHIsIGssIHQ7CiAgICBkb3sKICAgICAgICAvLyDQktGL0YfQuNGB0LvRj9C10LwgciAtINC90LDQuNC80LXQvdGM0YjQuNC5INC/0L7Qu9C+0LbQuNGC0LXQu9GM0L3Ri9C5INC+0YHRgtCw0YLQvtC6INC/0YDQuCDQtNC10LvQtdC90LjQuCB1INC90LAgdgogICAgICAgIHIgPSB1ICUgdjsKICAgICAgICAvLyDQktGL0YfQuNGB0LvRj9C10Lwg0YbQtdC70L7QtSBrID49IDAg0Lgg0L3QtdGH0LXRgtC90L7QtSB0OiByID0gdCAqIDJeawogICAgICAgIGsgPSB0ID0gMDsKICAgICAgICB3aGlsZShyICUgMiA9PSAwKQogICAgICAgIHsKICAgICAgICAgICAgaysrOyAgICAgICAgLy8g0J/QvtC60LDQt9Cw0YLQtdC70Ywg0YHRgtC10L/QtdC90Lgg0LTQstC+0LnQutC4INCyINGH0LjRgdC70LUgcgogICAgICAgICAgICByID4+PSAxOyAgICAvLyDQlNC10LvQuNC8IHIg0L3QsCAyCiAgICAgICAgfQogICAgICAgIHQgPSByOyAgICAgICAgICAvLyDQkiB0INC90LDRhdC+0LTQuNGC0YHRjyDRgNC10LfRg9C70YzRgtCw0YIg0LTQtdC70LXQvdC40Y8gciDQvdCwIDJeawogICAgICAgIHMgPSAocyArIGsgKiAodip2IC0gMSkvOCArICh0IC0gMSkqKHYgLSAxKS80KSAlIDI7CiAgICAgICAgaWYodCA9PSAxKQogICAgICAgICAgICByZXR1cm4gKHMpID8gLTEgOiAxOwogICAgICAgIC8vINCd0L7QstCw0Y8g0LjRgtC10YDQsNGG0LjRjwogICAgICAgIHUgPSB2OwogICAgICAgIHYgPSB0OwogICAgfXdoaWxlKHQgPj0gMyk7Cn0KCmludCBtYWluKCkgewoJc3RkOjpjb3V0IDw8IGphY29iaSg2LCAxMSkgPDwgc3RkOjplbmRsOyAJCS8vIC0xCglzdGQ6OmNvdXQgPDwgamFjb2JpKDIyNiwgMTM1KSA8PCBzdGQ6OmVuZGw7CQkvLyAxCglzdGQ6OmNvdXQgPDwgamFjb2JpKDI2LCAzNSkgPDwgc3RkOjplbmRsOwkJLy8gLTEKCXN0ZDo6Y291dCA8PCBqYWNvYmkoODg4LCAxOTk5KSA8PCBzdGQ6OmVuZGw7CS8vIC0xCiAgICBzdGQ6OmNvdXQgPDwgamFjb2JpKDg5MywgOTk3KSA8PCBzdGQ6OmVuZGw7CiAgICByZXR1cm4gMDsKfQ==