D. Frequency Sequence
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given a positive integer $$$s$$$ as its first term, a sequence of positive integers $$$a_1, a_2, \ldots$$$ is defined as follows.

  • $$$a_1 = s$$$
  • $$$a_{i+1} = \lvert \{ j \in \{1, 2, \ldots, i \} \mid a_j = a_i \} \rvert$$$ $$$\quad$$$ ($$$i \ge 1$$$)

That is, the $$$(i+1)$$$-th term $$$a_{i+1}$$$ is the number of times the value of its directly preceding term $$$a_i$$$ appears among the first through the $$$i$$$-th terms. For example, when $$$s = 3$$$, the first $$$12$$$ terms of the sequence are $$$3, 1, 1, 2, 1, 3, 2, 2, 3, 3, 4,$$$ and $$$1.$$$

Given two positive integers $$$s$$$ and $$$k$$$, find the value of $$$a_k$$$, the $$$k$$$-th term of the sequence.

Input

The input contains one or more test cases, each in the following format.

$$$s$$$ $$$k$$$

A test case consists of two positive integers $$$s$$$ and $$$k$$$ ($$$1 \le s \le 10^9$$$, $$$1 \le k \le 10^9$$$).

The end of the input is indicated by a line containing two zeros. The number of test cases does not exceed $$$100$$$.

Output

For each test case, output in a line the value of $$$a_k$$$, the $$$k$$$-th term of the sequence.

Example
Input
3 1
3 2
3 3
3 4
3 5
6 100
100000000 100000000
123456789 987654321
31415926 535897932
0 0
Output
3
1
1
2
1
12
50000000
5
16621598