#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;
}