- Language:
- Time limit: 1.00 s
- Memory limit: 512 MB
Joka askeleella pallo liikkuu ruudun vaaka- ja pystysuunnassa. Pallon suunta muuttuu aina, kun se kimpoaa reunasta tai kulmasta.
Seuraava kuva näyttää esimerkkinä, miten pallo alkaa liikkua $3 \times 4$ -ruudukossa. Pallon sininen väri tarkoittaa tilannetta, jolloin suunta muuttuu.
Syöte
Ensimmäisellä rivillä on kokonaisluku $t$: testien määrä.
Tämän jälkeen on $t$ riviä, joista jokaisella on kolme kokonaislukua $n$, $m$ ja $k$: ruudukon koko ja askelten määrä.
Tuloste
Tulosta jokaisen testin vastaus omalle rivilleen.
Esimerkki 1
Syöte:
8
3 4 0
3 4 1
3 4 2
3 4 3
3 4 4
3 4 5
3 4 6
3 4 7
Tuloste:
0
0
1
2
3
3
4
4
Esimerkki 2
Syöte:
3
2 2 100
111 222 999999
1337 42 123456789
Tuloste:
100
13573
3101295
Osatehtävä 1 (10 pistettä)
- $1 \le t \le 100$
- $2 \le n,m \le 10$
- $0 \le k \le 100$
- $1 \le t \le 1000$
- $2 \le n,m \le 10$
- $0 \le k \le 10^{18}$
- $1 \le t \le 1000$
- $2 \le n,m \le 10^9$
- $0 \le k \le 10^{18}$