문제

"^" 혹은 ""로 표기되는 bitwise xor 연산이란, 각각의 수를 이진수로 나타냈을 때 각각의 비트에 대하여 대응되는 두 비트가 같으면 , 다르면 을 반환하는 연산이다.

예를 들어, ^은 다음과 같이 구할 수 있다.

다섯 번째, 네 번째, 세 번째, 첫 번째 비트는 다르므로 , 두 번째 비트는 같으므로 이다. 따라서, ^은 다음과 같다.

^ =

xor의 유래를 거슬러 올라가보면, 피타고라스의 xor정리가 나온다.

피타고라스의 xor정리란, 한 변이 이고 나머지 두 변이 , 인 삼각형의 세 변은 ^ ^ ^라는 조건을 만족한다는 것이다.

예를 들어, 유명한 피타고라스 수인 , , 는 다음 조건을 만족한다.

^ , ^ , ^

따라서, 로 피타고라스의 xor정리를 만족한다.

이때, 세 변이 모두 길이 이하이고, 피타고라스의 xor정리를 만족시키는 삼각형을 찾아라.

입력

첫째 줄에 정수 이 주어진다. ()

출력

첫째 줄에 세 변의 길이가 모두 이하인 피타고라스의 xor정리를 만족시키는 삼각형의 개수를 출력한다.

둘째 줄부터 세 변의 길이가 모두 이하인 피타고라스의 xor정리를 만족시키는 삼각형의 세 변을 오름차순으로 출력한다. 이때, 출력한 결과가 사전 순으로 가장 앞서도록 한다.

예제 설명

예제에 나온 각각의 삼각형은 다음과 같다.

^^ = ^

^^ = ^

^^ = ^

^^ = ^

^^ = ^