import java.math.*;
class M{
}
public static void main
(String[] a
){ System.
out.
println(c
(1,
2,
1)); System.
out.
println(c
(1,
2,
2)); System.
out.
println(c
(13,
7,
27)); System.
out.
println(c
(2,
3,
1)); System.
out.
println(c
(4,
5,
7)); System.
out.
println(c
(4,
5,
0)); System.
out.
println(c
(9999,
23,
0)); System.
out.
println(c
(12345613,
2321,
89)); }
}
aW1wb3J0IGphdmEubWF0aC4qOwpjbGFzcyBNewogIHN0YXRpYyBTdHJpbmcgYyhpbnQuLi4gYSl7CiAgICByZXR1cm4gbmV3IEJpZ0RlY2ltYWwoYVswXSkuZGl2aWRlKG5ldyBCaWdEZWNpbWFsKGFbMV0pLCBhWzJdLCAzKSsiIjsKICB9CgogIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGEpewogICAgU3lzdGVtLm91dC5wcmludGxuKGMoMSwgMiwgMSkpOwogICAgU3lzdGVtLm91dC5wcmludGxuKGMoMSwgMiwgMikpOwogICAgU3lzdGVtLm91dC5wcmludGxuKGMoMTMsIDcsIDI3KSk7CiAgICBTeXN0ZW0ub3V0LnByaW50bG4oYygyLCAzLCAxKSk7CiAgICBTeXN0ZW0ub3V0LnByaW50bG4oYyg0LCA1LCA3KSk7CiAgICBTeXN0ZW0ub3V0LnByaW50bG4oYyg0LCA1LCAwKSk7CiAgICBTeXN0ZW0ub3V0LnByaW50bG4oYyg5OTk5LCAyMywgMCkpOwogICAgU3lzdGVtLm91dC5wcmludGxuKGMoMTIzNDU2MTMsIDIzMjEsIDg5KSk7CiAgfQp9