Perfect Square Sum Sequence

You are given a positive integer k. Your task is to compute the k-th term of a sequence \(\{a_n\}\) defined as follows:

• \(a_1 = 1\).
• For \(n \ge 2\), \(a_n\) is the smallest integer greater than \(a_{n-1}\) such that \(a_{n-1} + a_n\) is a perfect square.

A number \(x\) is a perfect square if there exists an integer \(s\) such that \(s^2 = x\). For example, the first few terms of the sequence are: 1, 3, 6, 10, 15, \(\dots\)

Compute and output the k-th term of this sequence.

inputFormat

The input consists of a single integer k (1 ≤ k), which indicates that you need to compute the k-th term of the sequence.

The input is provided via standard input (stdin).

outputFormat

Output a single integer, which is the k-th term of the sequence. The output should be printed to standard output (stdout) without any extra spaces or characters.

1

1