## Prime Game February long challenge 2021 solution with code and explanation -

### Problem statement -

Chef and Divyam are playing a game with the following rules:

- First, an integer is written on a board.
- Chef and Divyam alternate turns; Chef plays first.
- In each move, the current player should choose a positive integer which is divisible by up to distinct primes and does not exceed the integer currently written on the board. Note that is not a prime.
- is then subtracted from the integer on the board, i.e. if the integer written on the board before this move was , it is erased and replaced by .
- When one player writes on the board, the game ends and this player wins.

Given and , determine the winner of the game.

### Input

- The first line of the input contains a single integer denoting the number of test cases. The description of test cases follows.
- The first and only line of each test case contains two space-separated integers and .

### Output

For each test case, print a single line containing the string `"Chef"`

if Chef wins the game or `"Divyam"`

if Divyam wins (without quotes).

### Constraints

### Subtasks

Subtask #1 (5 points):

Subtask #2 (10 points):

Subtask #3 (85 points): original constraints

### Example Input

```
3
1 2
3 1
2021 42
```

### Example Output

```
Chef
Divyam
Divyam
```

### Explanation

Example case 1: Since is divisible by primes, Chef will write and win the game in the first move.

Example case 2: Chef must choose between and inclusive since is divisible by more than one prime. Then, Divyam can always choose , write on the board and win the game.

## Comments

## Post a Comment